DPcontest E (ナップザック問題)

ナップザック問題のversion2.価値に制限がある場合.重さに制限がある場合と解き方が異なります.

DPで解く

ナップザック問題といえばおなじみのDPですが今回はDPの定義が難しい.いつもの重さに制限がある場合は

    dp[i][j] : i 個まで見た時の重さが j 以下の{価値}の最大値

としていましたが今回は

    dp[i][j] : i 番目まで見た時の 価値を j にする時の{重さ}の最小値

と定義します.価値を表すか重さを表すかが違います。
漸化式の条件としては

    dp[0][0] = 0;
    dp[0][1  ...  n - 1]  = inf
    dp[i][j] = min ( dp[i - 1][j]  ,  dp[i - 1][j - value[i]] + w[i] )    { j - value[i] >= 0 }

となります.
難しい.. 最初のdpの方法に慣れてしまっているため今回のdpがしっくりこない.とりあえず書いてみよう.

1       long dp[][] = new long[n + 1][100001];

2       for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < 100001; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
3       dp[0][0] = 0;
4       for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < 100001; j++) {
                if (j - v[i] >= 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }