哄女朋友開心的錯誤示范。
題意：你和你女朋友（不，你沒有）去購物，你有兩個購物券v1，v2，不能疊加使用，所購買的禮物的和不超過券的值就可以買，你女朋友過生日，可以免費帶走一個禮物。禮物有價格p和女朋友開心值v，有些禮物是你女朋友必須要的，你必須要買的。求女朋友開心值（所得到的v的和）的最大值。
思路：01背包的變形，二維背包、帶約束條件的背包、（僅）可消除一次價格、提醒你沒有女朋友 。
dp[i][j][k]表示v1使用了i元,v2使用了j元,k==1代表你女朋友已經(jīng)免費帶走一個商品（技能CD中 ） 。
狀態(tài)轉(zhuǎn)移方程：
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]要放在前面，否則會重復(fù)記一個。

那么怎么處理女朋友必買的物品呢？
我的思路是在必買的物品加上1000000，這里的物品的價格和最大不過300*1000=300000，在加上后必買的物品的價格會嚴格高于其他物品，且不會出現(xiàn)其余物品和加起來大于1000000的情況，在結(jié)尾判斷一下ans整除1000000的值，這個值就是你必買禮物的個數(shù)了，輸出的時候記得減掉，輸出時候要兩個\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+1inline 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_Zhifengfreopen("in.txt", "r", stdin); #endifint 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; }

總結(jié)

以上是生活随笔為你收集整理的HDU 3236 Gift Hunting (程序猿的哄女朋友方式)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。