哄女朋友开心的错误示范。 题意：你和你女朋友（不，你没有）去购物，你有两个购物券v1，v2，不能叠加使用，所购买的礼物的和不超过券的值就可以买，你女朋友过生日，可以免费带走一个礼物。礼物有价格p和女朋友开心值v，有些礼物是你女朋友必须要的，你必须要买的。求女朋友开心值（所得到的v的和）的最大值。 思路：01背包的变形，二维背包、带约束条件的背包、（仅）可消除一次价格、提醒你没有女朋友 。 dp[i][j][k]表示v1使用了i元,v2使用了j元,k==1代表你女朋友已经免费带走一个商品（技能CD中 ） 。 状态转移方程： dp[j][k][1] = max(dp[j][k][1], dp[j][k][0]+v[i]); dp[j][k][0] = max(dp[j][k][0], dp[j-p[i]][k][0]+v[i]); dp[j][k][1] = max(dp[j][k][1], dp[j-p[i]][k][1]+v[i]) dp[j][k][0] = max(dp[j][k][0], dp[j][k-p[i]][0]+v[i]); dp[j][k][1] = max(dp[j][k][1], dp[j][k-p[i]][1]+v[i]); 其中从dp[j][k][0]到dp[j][k][1]要放在前面，否则会重复记一个。
那么怎么处理女朋友必买的物品呢？ 我的思路是在必买的物品加上1000000，这里的物品的价格和最大不过300*1000=300000，在加上后必买的物品的价格会严格高于其他物品，且不会出现其余物品和加起来大于1000000的情况，在结尾判断一下ans整除1000000的值，这个值就是你必买礼物的个数了，输出的时候记得减掉，输出时候要两个\n…
代码：
#include <algorithm> #include <iostream> #include <cstdio> #include <stack> #include <vector> #include <string> #include <cstring> #include <cmath> #include <queue> #include <set> #include <map> #include <list> #include <ctime> using namespace std; #define ll long long #define ld long double #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define EXP 1e-8 #define MOD 1000000007 #define N 50005 #define random(x) rand()%x+1 inline int next_int() { char c; while(c = getchar(), c < '0' || c > '9'); int r = c-'0'; while(c = getchar(), c >= '0' && c <= '9') r = r*10+c-'0'; return r; } int n, v1, v2; int dp[502][55][2]; int p[505]; int v[505]; int need[505]; int numbOfNeed; int ans; void init() { memset(dp, 0, sizeof(dp)); memset(p, 0, sizeof(p)); memset(v, 0, sizeof(v)); memset(need, 0, sizeof(need)); numbOfNeed = 0; ans = 0; } int main() { #ifdef Wang_Zhifeng freopen("in.txt", "r", stdin); #endif int cnt = 1; while(scanf("%d%d%d", &v1, &v2, &n)) { if(n==0)break; init(); for(int i = 0; i < n; ++i) { scanf("%d%d%d", &p[i], &v[i], &need[i]); if(need[i]==1) { numbOfNeed++; v[i] += 1000000; } } for(int i = 0; i < n; ++i) { for(int j = v1; j >= 0; --j) { for(int k = v2; k >= 0; --k) { dp[j][k][1] = max(dp[j][k][1], dp[j][k][0]+v[i]); if(j >= p[i]) { dp[j][k][0] = max(dp[j][k][0], dp[j-p[i]][k][0]+v[i]); dp[j][k][1] = max(dp[j][k][1], dp[j-p[i]][k][1]+v[i]); } if(k >= p[i]) { dp[j][k][0] = max(dp[j][k][0], dp[j][k-p[i]][0]+v[i]); dp[j][k][1] = max(dp[j][k][1], dp[j][k-p[i]][1]+v[i]); } } } } for(int j = v1; j >= 0; --j) { for(int k = v2; k >= 0; --k) { ans = max(ans, dp[j][k][0]); ans = max(ans, dp[j][k][1]); } } printf("Case %d: %d\n\n", cnt++, ans >= numbOfNeed*1000000 ? ans-numbOfNeed*1000000 : -1); } return 0; }