ナップサック2 O(NV) ～weightが大きい場合～

• Quiz
  • http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_F
• AC
  • http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4876929#1
• 解説
  • 蟻本にある
  • 普通のナップサックはO(NW)でdpテーブルを「個数」「容量」で持つが、今回はWが大きいので別の視点のテーブルとする
• 計算量
  • N 個数
  • V すべてを取得した場合の価値の合計
  • として、O(NV)

ll dp[110][15000];
// i番目まで見て
// 価値jを達成する時に必要な最小の重さ

code

ll dp[110][15000];
// i番目まで見て
// 価値jを達成する時に必要な最小の重さ

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,W;
    cin>>N>>W;

    rep(i,110){
      rep(j,15000){
        dp[i][j]=inf;
      }
    }
    dp[0][0]=0;

    rep(i,N){
      ll v,w;cin>>v>>w;

      rep(j,10000){
        // 現在の価値j

        // とる
        chmin(dp[i+1][j+v], dp[i][j]+w);

        // とらない
        chmin(dp[i+1][j], dp[i][j]);
      }
    }
    ll max_value=0;
    rep(v,15000){
      if(dp[N][v]<=W){
        // 条件を満たす
        chmax(max_value, v);
      }
    }
    p(max_value);
    
    return 0;
}