個数制限付きナップサック

  • Quiz
  • AC
  • 解説
    • tsutajさんのBlogを読んだ
    • 各品物を1, 2, 4, 8個... に分解して、採用・非採用で分岐していけばmの箇所のオーダーはlog(m)になる
    • 他は普通の荷持1個だけナップサックと同じ
  • その他
    • 蟻本に載っていそうで載っていなかった
    • うしさんのライブラリではスライド最小値を使ってlogを消しているみたい
  • 計算量
    • N 種類数 (100)
    • W 容量 (10000)
    • m 選べる個数の最大値(10000)
    • O(N W log m) = 100 x 10000 x log(10000) = 1.5 x 107程度
int main(){
    // input
    ll N,C;
    cin>>N>>C;

    VI V(N);
    VI W(N);
    VI M(N);
    rep(i,N)cin>>V[i]>>W[i]>>M[i];

    VI dp(C+1,-1); // capacityまで確保しておけばよかろう
    dp[0]=0;

    // for文が3重であるが、順番に注意
    rep(i,N){
      ll m = M[i]; // 最大個数
      rep(j,15){
        ll num = 1<<j; // i番目をnum個、加える or 加えない
        num = min(num, m); // 個数上限を超えないように
        if(num==0) break;

        for(int w=C-1; w>=0; w--){ // 重さwからの遷移
          if(dp[w]==-1)continue;
          if(w+W[i]*num<=C){
            chmax(dp[w+W[i]*num], dp[w] + V[i]*num);
          }
        }
        m -= num;
      }
    }
    
    ll ma = 0;
    rep(w,C+1){
      chmax(ma, dp[w]);
    }
    p(ma);
    
    return 0;
}