動的計画法でナップサック問題を解く
動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。
なぜでしょうか?
1から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。
多くの解説ではdpテーブルの遷移を
dp[i][p]: i-1 番目までの品物から重さが p を超えないように選んだときの、価値の総和の最大値
としていますが、これを
i番目(i-1ではない)までの品物から重さがpを超えないように選ぶ時の価値の総和の最大値とすることはできるのでしょうか?
https://atcoder.jp/contests/dp/tasks/dp_d
問題文
N個の品物があります。 品物には 1,2,…,N と番号が振られています。 各 i (1≤i≤N) について、品物 i の重さは wi
で、価値は vi です。太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W
であり、持ち帰る品物の重さの総和はW以下でなければなりません。太郎君が持ち帰る品物の価値の総和の最大値を求めてください。
制約 入力はすべて整数である。 1≤N≤100 1≤W≤105 1≤wi≤W 1≤vi≤109
#include <bits/stdc++.h>
using lli = long long int;
template <typename T>
bool chmax(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
lli n, w;
std::vector<std::pair<lli, lli>> vec;
std::vector<std::vector<lli>> dp;
int main() {
std::cin >> n >> w;
vec.assign(n+1, {0, 0});
for (lli i = 0; i < n; i++) {
std::cin >> vec[i].first >> vec[i].second;
}
dp.assign(n+1, std::vector<lli>(w+1, 0));
for (lli i = 1; i <= n; i++) {
for (lli p = 0; p <= w; p++) {
if (p >= vec[i].first) {
chmax(dp[i][p], dp[i-1][p-vec[i].first] + vec[i].second);
}
else {
chmax(dp[i][p], dp[i-1][p]);
}
}
}
std::cout << dp[n][w] << std::endl;
}