题目描述:
Taotao的电脑带不动绝地求生,所以taotao只能去玩pc版的荒野行动了,和绝地求生一样,游戏人物本身可携带一定重量m的物品,装备背包之后可以多携带h(h为0代表没有装备背包)重量的东西。玩了几天taotao发现了一个BUG,当装备背包之后,如果可携带重量没有满,就可以拿一个任意重的东西。(解释看样例)有一天taotao空降到了一个奇怪的岛上,岛上有n件装备,每个装备都有重量Wi和威力值Vi,但taotao不认识这些装备,所以他来求助你,挑选威力最大的装备,帮助他吃鸡。
思路:
首先他是一个背包问题,我们就可以在外层枚举第i个物品,进行取或者不取的情况讨论并取得最优解。则可推出它的状态转移方程:
dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
由于一个子问题的最优解只需要前一个状态的最优解所以我们可以把二维转换成一维
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
这部分代码就是
memset(dp,0, sizeof(dp)); for(int i=1;i<=n;i++) { for(int j=m+h;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); }
但是由于题目有个额外的条件所以不能就那么算了。由于当装备背包之后,如果可携带重量没有满,就可以拿一个任意重的东西。所以可以找出当h不为0时可以卡bug的时候,的最大值。
for(int k=1;k<=n;k++)//枚举用k来找卡bug时取k的最优解 { memset(dp,0, sizeof(dp)); for(int i=1;i<=n;i++) { if(i==k)continue; for(int j=m+h;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } if(h)ans=max(ans,dp[m+h-1]+v[k]);//当装备了背包时最优解为背包未满时加上k物品的威力 else ans=max(ans,dp[m+h]); }
完整ac代码:
#include<bits/stdc++.h> using namespace std; int w[105],v[105]; int dp[205]; int main() { int n,m,h; while(cin>>n) { if(n==0)break; cin>>m>>h; int ans=0; for(int i=1;i<=n;i++)cin>>w[i]>>v[i]; for(int k=1;k<=n;k++) { memset(dp,0, sizeof(dp)); for(int i=1;i<=n;i++) { if(i==k)continue; for(int j=m+h;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } if(h)ans=max(ans,dp[m+h-1]+v[k]); else ans=max(ans,dp[m+h]); } printf("%d\n",ans); } return 0; }