题目链接：https://atcoder.jp/contests/abc145/tasks/abc145_e
题意：有n道菜，每道菜需要a[i]分吃完，能获得b[i]的美味值 给T分钟，问怎么样吃，才能在T内得到最多的美味值，
一旦开始了吃就一定会吃完这道菜，哪怕时间超过T分
思路：很明显的01背包问题，不过是多了一个 某一道菜不受时间限制 的条件 很容易看出这里的一个 贪心就是 用1分钟给一道菜 这样是最优解
那么 此时的T就变为T-1 然后考虑01背包dp
加一维的空间满足 他有没有用上这 1分钟的条件 ，1为有 0为没有
关键的转移是 在x等于1的时候也要 用上
if(j>=w[i])
{
dp[i][j][x]=max(dp[i][j][x],dp[i-1][j-w[i]][x]+v[i]);
} 当已经使用了这个条件后， 此时就和0 的时候是等价的 ，剩下的也是转换为取和不取的问题， 否则 的话 1的状态无法延续下去
二维01背包的代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 #define pb push_back 6 const int maxn=1e6+10; 7 const int mod=1e9+7; 8 const double pi=3.1415926535; 9 int w[3005],v[3005]; 10 int dp[3005][3005][2]; 11 12 13 14 15 int main() 16 { 17 ios::sync_with_stdio(false); 18 cin.tie(0); 19 int n,t; 20 cin>>n>>t; 21 for(int i=1;i<=n;i++) 22 { 23 cin>>w[i]>>v[i]; 24 } 25 for(int i=1;i<=n;i++) 26 { 27 for(int j=0;j<=t-1;j++) 28 { 29 for(int x=0;x<=1;x++) 30 { 31 if(x==0) 32 { 33 if(j>=w[i]) 34 { 35 dp[i][j][x]=max(dp[i-1][j][x],dp[i-1][j-w[i]][x]+v[i]); 36 } 37 else 38 { 39 dp[i][j][x]=dp[i-1][j][x]; 40 } 41 } 42 else 43 { 44 dp[i][j][x]=max(dp[i-1][j][x],dp[i-1][j][0]+v[i]); 45 if(j>=w[i]) 46 { 47 dp[i][j][x]=max(dp[i][j][x],dp[i-1][j-w[i]][x]+v[i]); 48 } 49 } 50 } 51 } 52 } 53 cout<<dp[n][t-1][1]<<‘\n‘; 54 55 56 57 58 59 60 }
也可以优化成一维01背包的代码
要注意的是 先 更新1 在更新0 不然会重复
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define ull unsigned long long 5 #define pb push_back 6 const int maxn=1e6+10; 7 const int mod=1e9+7; 8 const double pi=3.1415926535; 9 int w[3005],v[3005]; 10 int dp[3005][2]; 11 12 13 14 15 int main() 16 { 17 ios::sync_with_stdio(false); 18 cin.tie(0); 19 int n,t; 20 cin>>n>>t; 21 for(int i=1;i<=n;i++) 22 { 23 cin>>w[i]>>v[i]; 24 } 25 for(int i=1;i<=n;i++) 26 { 27 for(int j=t-1;j>=0;j--) 28 { 29 for(int x=1;x>=0;x--) 30 { 31 if(x==0) 32 { 33 if(j>=w[i]) 34 { 35 dp[j][x]=max(dp[j][x],dp[j-w[i]][x]+v[i]); 36 } 37 } 38 else 39 { 40 dp[j][x]=max(dp[j][x],dp[j][0]+v[i]); 41 if(j>=w[i]) 42 { 43 dp[j][x]=max(dp[j][x],dp[j-w[i]][x]+v[i]); 44 } 45 } 46 } 47 } 48 } 49 cout<<dp[t-1][1]<<‘\n‘; 50 51 52 53 54 55 56 }
AtCoder Beginner Contest 145 E - All-you-can-eat
原文：https://www.cnblogs.com/winfor/p/13284368.html
