perogram

Invest Master (AOJ 2607) ”個数制限なし”ナップサック

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607

AC

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4008533#1

解法

  • 毎日売ると考えてよいので、今日と明日だけを見て利益を最大化すればいい
  • 画像のように荷物に置き換えて、個数制限なしナップサック問題を毎日解けばいい
  • コードは蟻本p58にある

f:id:peroon:20191126153255p:plain

Code

  • 自分なりに再利用可能にしてみた (※個数制限なし)
  • 何度もDPするので、毎回DPテーブルを初期化することを忘れずに
// i : N+1
// j : capacity
ll dp[11][100010];
void reset(){
  rep(i, 11){
    rep(j, 100010){
      dp[i][j] = 0;
    }
  }
}

// !!!個数制限なし!!!ナップサック
// V : value
// W : weight
// C : capacity
ll knapsack(VI& V, VI& W, ll C){
  reset();
  ll n = V.size();
  rep(i, n){
    rep(j, C+1){
      if(j<W[i]){
        dp[i+1][j] = dp[i][j];
      }else{
        dp[i+1][j] = max(dp[i][j], dp[i+1][j-W[i]] + V[i]);
      }
    }
  }
  return dp[n][C];
}