Eat Snacks

2 secs 1024 MB

$dp[i][j]$ : $\:$ $i$ 個目までのお菓子のなかで、合計が $j$ グラムのお菓子から摂取できるカロリーの最大値
という DP が直感的に思い浮かびますが、今回の問題ではお菓子の重量がとても大きいため、この DP では解くのに時間がかかってしまいます。

$dp[i][j]$ : $\:$ $i$ 個目までのお菓子のなかで、 $j$ カロリーを摂取するための重さの最小値
という DP をすることによってこの問題を十分高速に解くことができます。

実装例(C++)

#include <bits/stdc++.h>

using namespace std;

const long long INF = 0x1fffffffffffffff;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
  }
  for(int i = 0; i < n; i++){
    cin >> b[i];
  }
  vector<vector<long long>> dp(n+1, vector<long long>(101010, INF));
  dp[0][0] = 0;
  for(int i = 0; i < n; i++){
    for(int j = 0; j <= 100000; j++){
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
      dp[i+1][j+b[i]] = min(dp[i+1][j+b[i]], dp[i][j] + a[i]);
    }
  }
  int ans = 0;
  for(int i = 0; i <= 100000; i++){
    if(dp[n][i] <= k){
      ans = max(ans, i);
    }
  }
  cout << ans << endl;
}