C++でナップサック問題が解けなくて困っています

Question

最近プログラミングを始めた初心者なのですが、最近dpを学び始めました。

次の問題に提出をしたのですが、ACが出なくて困っています。色々と問題がありそうなところは修正してみたのですが、どうにも入力されるデータが大きいと正しい答えが出力できていないようです。言語はC++(GCC 9.2.1)です。どなたか、アドバイスお願いします。

提出したコードおよび問題は以下のリンクです。
Educational DP Contest D-Knapsack 1

何卒よろしくお願い申し上げます。

リンク先のコードです

#include<bits/stdc++.h>
using namespace std;
 
 
int main() {
    long long n, w;
    cin >> n >> w;
    long long wei[n], val[n];
    long long dp[200010][110];
 
    for (long long i = 0; i < n; i++){
        cin >> wei[i] >> val[i];
    }
 
    for (long long i = 0; i < 200010; i++){
        for (long long j = 0; j < 110; j++){
            dp[i][j] = 0;
        }
    }
 
    dp[wei[0]][0] = val[0];
    dp[wei[0]][1] = val[0];
 
    for (long long i = 1; i < n; i++){
        for (long long j = 0; j < w; j++){
            dp[j + wei[i]][i] = max(dp[j + wei[i]][i], max(dp[j + wei[i]][i], dp[j][i - 1] + val[i]));
            dp[j + wei[i]][i + 1] = dp[j + wei[i]][i];
            dp[j + wei[i] + 1][i] = max(dp[j + wei[i] + 1][i], dp[j + wei[i]][i]);
        }
    }
 
    cout << dp[w][n - 1] << endl;
}

Comments

[y_waiwai]

コードを提示しよう

Answer 1

現状のコードだと、最終的に選ばれる品物と品物の間が2つ以上離れている場合に、情報が欠落する可能性があります。

例えば、以下の入力に対して、正しい出力は4(品物1,4を選ぶ)ですが、このコードだと3が返ります。

4 4
1 2
2 1
2 1
3 2

直接の原因は、dp[0][i]～dp[wei[i]-1][i]に対して何もやっていないことです。
本来であれば、こちらの範囲の値について、隣に値をコピーする処理が必要となります。

ただ、現状のコードは一般的なdpから外れているので、まずは「ナップサック問題 動的計画法」あたりで検索して、正しいやり方を調べることをお勧めします。

Comments

[vi_24E]

回答ありがとうございます。
つまりdp漸化式の部分が間違えているということですよね？
もう少し調べながら試行錯誤してみます。

[vi_24E]

無事解決し、ACだせました！

https://atcoder.jp/contests/dp/submissions/27632247

[vi_24E]

./Main.cpp: In function ‘int main()’:
./Main.cpp:15:23: warning: array subscript 200000 is above array bounds of ‘long long int [200000]’ [-Warray-bounds]
15 | dp[110][200000] = -1;
| ~~~~~~~~~~~~~~^

よかったら、このエラーコードの原因を教えていただけますか？

[退会済みユーザー]

メッセージちゃんと読めばすぐ判る。判らないならgoogle翻訳や検索を駆使しなさい。