题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3236
题目链接：某人有两张卡，卡上的钱不能合并消费，买东西的时候物品有两个属性，一个是必须买的，还有一个不是必须买的，同一样物品用不同的卡消费相同并且只能购买一次，我们需要最大的价值(即happy值)，你还有一张优惠券进行免费消费一次。
Sample Input
3 2 4 3 10 1 2 10 0 5 100 0 5 80 0 3 2 4 3 10 1 2 10 0 5 100 0 5 80 1 0 0 0
Sample Output
Case 1: 120 Case 2: 100
emmm，两张卡，不能合并消费，那么也就是2个背包问题了，多了个免费券，那么我们再开一维来记录券的使用情况就OK了，那么状态转移方程也不难写出来
对于必须买的物品，我们直接往里面塞：
int tot=0,pre=0; memset(dp,0,sizeof dp); for (int i=1; i<=special; i++) { pre=tot;//必须把前i-1个都拿了才能作为转移状态 tot+=sp[i].h; for (int j=v1; j>=0; j--) { for (int k=v2; k>=0; k--) { if (dp[j][k][0]==pre) dp[j][k][1]=tot; if (j-sp[i].p>=0) { if (dp[j-sp[i].p][k][1]==pre) dp[j][k][1]=tot; if (dp[j-sp[i].p][k][0]==pre) dp[j][k][0]=tot; } if (k-sp[i].p>=0) { if (dp[j][k-sp[i].p][1]==pre) dp[j][k][1]=tot; if (dp[j][k-sp[i].p][0]==pre) dp[j][k][0]=tot; } } } }
那么如果能够买完所有特殊物品，则背包最大容量的价值一定会等于所有特殊物品的价值，也就是$dp[v1][v2][1]==tot$
接下来就是一个比较有点技巧的操作，我们将没有装满特殊物品的状态打上标记，用来表示该状态不能作为转移状态，然后开始对普通物品跑多个01背包了。其具体写法和特殊物品差不多，只不过多了个标记的判断而已。
以下是AC代码：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node { int p,h; }sp[320],nom[320]; int dp[510][60][5]; int main() { int v1,v2,n; int Case=0; while (scanf ("%d%d%d",&v1,&v2,&n)){ if (!v1 && !v2 && !n) return 0; int special=0,nomall=0; for (int i=1; i<=n; i++){ int p,h,s; scanf ("%d%d%d",&p,&h,&s); if (s) sp[++special]=node{p,h}; else nom[++nomall]=node{p,h}; } int tot=0,pre=0; memset(dp,0,sizeof dp); for (int i=1; i<=special; i++){ pre=tot;//必须把前i-1个都拿了才能作为转移状态 tot+=sp[i].h; for (int j=v1; j>=0; j--){ for (int k=v2; k>=0; k--){ if (dp[j][k][0]==pre) dp[j][k][1]=tot; if (j-sp[i].p>=0){ if (dp[j-sp[i].p][k][1]==pre) dp[j][k][1]=tot; if (dp[j-sp[i].p][k][0]==pre) dp[j][k][0]=tot; } if (k-sp[i].p>=0){ if (dp[j][k-sp[i].p][1]==pre) dp[j][k][1]=tot; if (dp[j][k-sp[i].p][0]==pre) dp[j][k][0]=tot; } } } } if (dp[v1][v2][1]<tot) {printf("Case %d: -1\n\n",++Case); continue;} for (int i=0; i<=v1; i++) for (int j=0; j<=v2; j++) for (int k=0; k<=1; k++) if (dp[i][j][k]!=tot) dp[i][j][k]=-1;//没有装满特殊物品的状态不能作为转移状态 for (int i=1; i<=nomall; i++){ for (int j=v1; j>=0; j--){ for (int k=v2; k>=0; k--){ if (dp[j][k][0]!=-1) dp[j][k][1]=max(dp[j][k][1],dp[j][k][0]+nom[i].h); for (int o=0; o<=1; o++){ if (dp[j][k][o]==-1) continue; if (j-nom[i].p>=0){ if (dp[j-nom[i].p][k][o]!=-1) dp[j][k][o]=max(dp[j][k][o],dp[j-nom[i].p][k][o]+nom[i].h); } if (k-nom[i].p>=0){ if (dp[j][k-nom[i].p][o]!=-1) dp[j][k][o]=max(dp[j][k][o],dp[j][k-nom[i].p][o]+nom[i].h); } } } } } printf("Case %d: %d\n\n",++Case,dp[v1][v2][1]); } return 0; }
原文：https://www.cnblogs.com/lonely-wind-/p/13263622.html