解法

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

f:id:peroon:20191126153255p:plain

code

自分なりに再利用可能にしてみた (※個数制限なし)
何度もDPするので、毎回DPテーブルを初期化することを忘れずに

// i : 個数
// j : capacity
const int N_MAX = 100; // 個数
const int CAPACITY_MAX = 10000; // キャパシティ
ll dp[N_MAX+1][CAPACITY_MAX+1];
void reset(){
  rep(i, N_MAX+1){
    rep(j, CAPACITY_MAX+1){
      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];
}