EDPC E-Knapsack

EDPC E-Knapsack

問題

E - Knapsack 2

N個の品物があります。
品物には 1,2,…,Nと番号が振られています。
各 i (1≤i≤N) について、品物 iの重さは wiで、価値は viです。

太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は W
であり、持ち帰る品物の重さの総和は W以下でなければなりません。

太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約
　入力はすべて整数である。
　1<=N<=100
　1<=W<=10e9
　1<=wi<=W
　1<=vi<=1000

練習ポイント

ナップサックで荷物の番号、価値、重さの要素のうち、重さが大きくてdpの変数にできないパターン。
代わりに価値をdpの変数においてやる。dp[番号][価値]

テーブルの組み方と解答の出力が間違えやすく自力で一から書けるよう何度も練習する。

WAしたコード

DPテーブルの理解が甘い。

i番目をとったときは新たにとったv[i]を加えてsum_vになるので，

dp[i+1][sum_v]=min(dp[i+1][sum_v],dp[i][sum_v-v[i]]+w[i]);

としなければならない。

    for (int i = 0; i < N; i++) {
        for (int sum_v = 0; sum_v < 100009; sum_v++) {
　　　//とったとき
            if (sum_v - v[i] >= 0) {
                dp[i + 1][sum_v+v[i]] = min(dp[i + 1][sum_v+v[i]], dp[i][sum_v+v[i]] + w[i]);
            }
　　　//とらないとき
            dp[i + 1][sum_v] = min(dp[i][sum_v], dp[i+1][sum_v]);
        }
    }

vの上限はしっかりmax_vまでとっておかないとエラーになる。

    long long ans = 0;
    for (long long sum_v = 0; sum_v < 100005; sum_v++) {
          if (dp[N][sum_v] <= W){
          ans = max(ans,sum_v);
          //cout<<ans<<"###"<<sum_v<<endl;
        }
    }
    cout << ans << endl;
    return 0;
}

ACしたコード

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

int main() {
    int N, W;
    cin >> N >> W;
    long long w[110];
    long long v[110];

    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    long long INF = 10000000000;
    long long dp[110][100010];

    //dpテーブルをINFで初期化
    for (int i = 0; i < N + 1;i++) {
        for (int j = 0; j < 100010; j++) {
            dp[i][j] = INF;
        }
    }
  
    dp[0][0] = 0;

    //dpループ
    for (int i = 0; i < N; i++) {
        for (int sum_v = 0; sum_v < 100009; sum_v++) {
            if (sum_v - v[i] >= 0) {
                dp[i + 1][sum_v] = min(dp[i + 1][sum_v], dp[i][sum_v - v[i]] + w[i]);
            }
            dp[i + 1][sum_v] = min(dp[i][sum_v], dp[i+1][sum_v]);
        }
    }

    long long ans = 0;
    for (long long sum_v = 0; sum_v < 100010; sum_v++) {
          if (dp[N][sum_v] <= W){
          ans = sum_v;
          //cout<<ans<<"###"<<sum_v<<endl;
        }
    }
    cout << ans << endl;
    return 0;
}