

動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。  
なぜでしょうか?

１から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。  
多くの解説ではdpテーブルの遷移を

[code]

    dp[i][p]: i-1 番目までの品物から重さが p を超えないように選んだときの、価値の総和の最大値
    
[/code]

としていますが、これを  
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
[code]

    #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;
    }
    
[/code]


CC BY-SA 4.0
2019-05-22T10:37:42.400
55167
2019-05-22T13:46:00.363
5246
question
c++ アルゴリズム データ構造
動的計画法でナップサック問題を解く

[code]

    #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;
            std::cin >> vec[i+1].first >> vec[i+1].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]);
                    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;
    }
    
[/code]

このコードでACすることを確認しました。おそらくペアの配列への入力の仕方がおかしかったのだと思われます。


CC BY-SA 4.0
2019-05-22T13:46:00.363
55177
2019-05-22T13:46:00.363
31249
55167
answer