題目大意：xx去買鞋，有k種牌子，然后給出n雙鞋，每雙鞋有它屬于的牌子、價格、收藏價值。xx認(rèn)為他不差錢，要求每種鞋子買一雙。但實(shí)際上他只有m毛錢，問能否買到符合xx要求的鞋，能找到的話輸出最大的收藏價值總和。 ? 分組背包的變形，每種牌子要求至少選一個，這與分組背包的每組最多選一個不一樣，但背包的思想都是一樣的。。。 就是狀態(tài)轉(zhuǎn)移的時候可以加上從上一組轉(zhuǎn)移（選擇1個）與本組轉(zhuǎn)移（大于1個），還有注意枚舉物品和枚舉體積的順序~~ 設(shè)dp[i][j]表示前i組填到容量j的最大價值， 則方程為：dp[i][j] = max(dp[i][j],dp[i-1][j-price[i][k]] + value[i][k],dp[i][j-price[[i][k]] + value[i][k]) ? #include #include #include #include #include #include #include #include #include #include #include #include #define MID(x,y) ((x+y)>>1) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std;typedef long long LL; const int sup = 0x7fffffff; const int inf = -0x7fffffff;struct shoes{int price;int value; }; vector s[11];int f[15][10100]; int N, M, K;int main(){while(scanf("%d %d %d", &N, &M, &K) != EOF){for (int i = 0; i < 11; i ++)s[i].clear();for (int i = 1; i <= N; i ++){int tmp_brand, tmp_price, tmp_value;scanf("%d %d %d", &tmp_brand, &tmp_price, &tmp_value);shoes tmp;tmp.price = tmp_price;tmp.value = tmp_value;s[tmp_brand].push_back(tmp);}mem(f, -1);f[0][0] = 0;for (int k = 1; k <= K; k ++)for (int j = 0; j < (int)s[k].size(); j ++)for (int v = M; v >= 0; v --){if (v-s[k][j].price >= 0 && f[k][v-s[k][j].price] != -1){f[k][v] = max(f[k][v], f[k][v-s[k][j].price]+s[k][j].value);}if (v-s[k][j].price >= 0 && f[k-1][v-s[k][j].price] != -1){f[k][v] = max(f[k][v], f[k-1][v-s[k][j].price]+s[k][j].value);}}int res = -1;for (int v = 0; v <= M; v ++)if (f[K][v] > res)res = f[K][v];if (res >= 0)printf("%d\n", res);elseprintf("Impossible\n");}return 0; } ?

轉(zhuǎn)載于:https://www.cnblogs.com/AbandonZHANG/archive/2013/03/20/4114229.html

總結(jié)

以上是生活随笔為你收集整理的HDU 3033 I love sneakers! (分组背包变形)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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