hogecoder

tsutaj 競技プログラミングの記録

AOJ DPL_1_G: Knapsack Problem with Limitations

個数制限付きナップザック問題です。

問題概要

原文 → Knapsack Problem with Limitations | Aizu Online Judge

価値  v_i で重さ  w_i であるような  N 種類の品物と、容量が  W のナップザックがある。

 i 番目の品物は  m_i 個まで使用できる。

ナップザックの容量を超えないように品物を入れた時の価値の最大値を求めよ。

解説

各品物について、品物を  1 個入れたとき、 2 個入れたとき・・・と愚直に  1 ずつ増やして考えていくと計算量的に間に合いません。

そこで、繰り返し二乗法のように(厳密には少し違うけど)、取る数を  2 倍ずつ増やしていくことで考えていきましょう。

例えば品物が  13 個ある場合は、この場合ですと

  • 品物を  1 個入れたとき
  • 品物を  2 個入れたとき
  • 品物を  4 個入れたとき
  • 品物を  6 個入れたとき

をそれぞれ計算するというわけですね。これで計算量が  O(NW \log m) となり間に合います。

ソースコード

for 文の向きに気をつけましょう。

signed main() {
    int N, W; cin >> N >> W;
    int v[110], w[110], m[110];
    rep(i,0,N) cin >> v[i] >> w[i] >> m[i];

    int dp[10010] = {};
    rep(i,0,N) {
        // take key good(s) each
        for(int k=0; m[i]>0; k++) {
            int key = min(m[i], (int)(1<<k));
            m[i] -= key;
            for(int j=W; j>=key*w[i]; j--) {
                // do not take or take
                dp[j] = max(dp[j], dp[j-key*w[i]] + key*v[i]);
            }
        }
    }
    int ans = 0;
    repq(i,0,W) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}