HDU 5410 (0 1背包+ 完全背包)

题意： 总钱M，种类N个，每个种类有价值w[i] ，个数a[i],b[i]，花一份价值，得a[i]个物品，送b[i]个（只赠送一次），求最多能拿的个数 题解：先根据a[i]+b[i]，01背包，再倒着背回a[i]，求出最大的a[i]的个数 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N=2005; const int M=2005; int m,n; int dp[M];//dp[i] 个数 i为钱 int a[N],b[N],w[N]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&m,&n); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d%d%d",&w[i],&a[i],&b[i]); for(int i=1;i<=n;i++) { // 0 1背包 出 拿b[i]一定要拿至少一个a[i] for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+a[i]+b[i]); // 往回背 背出尽可能多a[i] for(int j=w[i];j<=m;j++) dp[j]=max(dp[j],dp[j-w[i]]+a[i]); } printf("%d\n",dp[m]); } return 0; }