競技プログラミングのDPの問題が分かりません。

Question

前提・実現したいこと

問題：N 個の品物があります。i 番目の品物はそれぞれ重さと価値が w(i) v(i)​ となっています (0≤i≤N−1)。

これらの品物から重さの総和が W を超えないように選んだときの、価値の総和の最大値を求めてください。

入力は次の形式で与えられます。
N W

w(0) v(0)

w(1) v(1)

⋮

w(N-1) v(N-1)

問題URL : https://algo-method.com/tasks/308

発生している問題・エラーメッセージ

自分のコードでは不正解の理由がわからないです。自分的にはアルゴリズムは合っていると思うのですが、

該当のソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N,W;
    cin >> N >> W;
    int W[110],V[110];
    for(int i=0;i<N;i++) cin >> w[i] >> V[i];

    vector<vector<int>> dp(N+1, vector<int>(W + 1 , -1000)); //縦個数、横重さで実装
    dp[0][0] = 0;

    for(int i=0;i<N;i++){
        for(int j=0;j<W;j++){
            if(dp[i][j] >= 0){ 
                dp[i+1][j] = dp[i][j]; //何も選ばない場合はそのまま
                if(j+w[i] < W){
                    dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]] , dp[i][j] + V[i]); //i個目の重さ分増えた場所の価値は、もともとそこにあった価値と、dp[i][j]に価値を足したものの最大値 
                }
            }
        }
    }

    int res = -111110;

    for(int j=0;j<W;j++){
        if(dp[N][j] > res) res = dp[N][j]; //N個目選んだ時の様々な重さでの最大値が答え
    }

    cout << res << endl;


}

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

• 配列wの定義が大文字のWになっています
• 最大値いっぱいまで詰め込んだ場合が考慮されていません。以下の入力で0が出力されます。

1 1
1 1

• 同じ重さの場合、必ず先に現れた要素が採用されます。以下の入力で5が出力されます。

2 3
2 5
2 10

Comments

[oioimeister]

<code>```c++
#include <bits/stdc++.h>
using namespace std;

int main(){
int N,W;
cin >> N >> W;
int w[110],V[110];
for(int i=0;i<N;i++) cin >> w[i] >> V[i];

vector<vector<int>> dp(N+1, vector<int>(W + 1 , -1000)); //縦個数、横重さで実装
dp[0][0] = 0;

for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
if(dp[i][j] >= 0){
dp[i+1][j] = dp[i][j]; //何も選ばない場合はそのまま
if(j+w[i] <= W){
dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]] , dp[i][j] + V[i]); //i個目の重さ分増えた場所の価値は、もともとそこにあった価値と、dp[i][j]に価値を足したものの最大値
}
}
}
}

int res = -111110;

for(int j=0;j<=W;j++){
if(dp[N][j] > res) res = dp[N][j]; //N個目選んだ時の様々な重さでの最大値が答え
}

cout << res << endl;

}
```

上2つについては実装してみました。3番目はこのプログラムでは実装がむずかしそうに感じるのですが、どうでしょうか？

[oioimeister]

3番目実装できました！！
#include <bits/stdc++.h>
using namespace std;

int main(){
int N,W;
cin >> N >> W;
int w[110],V[110];
for(int i=0;i<N;i++) cin >> w[i] >> V[i];

vector<vector<int>> dp(N+1, vector<int>(W + 1 , -1000)); //縦個数、横重さで実装
dp[0][0] = 0;

for(int i=0;i<N;i++){
for(int j=0;j<=W;j++){
if(dp[i][j] >= 0){
dp[i+1][j] = max(dp[i][j],dp[i+1][j]); //何も選ばない場合はそのまま
if(j+w[i] <= W){
dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]] , dp[i][j] + V[i]); //i個目の重さ分増えた場所の価値は、もともとそこにあった価値と、dp[i][j]に価値を足したものの最大値
}
}
}
}

int res = -111110;

for(int j=0;j<=W;j++){
if(dp[N][j] > res) res = dp[N][j]; //N個目選んだ時の様々な重さでの最大値が答え
}

cout << res << endl;

}
ありがとうございました！！