題目大意：xx去買鞋，有k種牌子，然後給出n雙鞋，每雙鞋有它屬於的牌子、價格、收藏價值。xx認為他不差錢，要求每種鞋子買一雙。但實際上他只有m毛錢，問能否買到符合xx要求的鞋，能找到的話輸出最大的收藏價值總和。
解題思路：分組背包的變形，每種牌子要求至少選一個，這與分組的最多選一個不一樣，但背包的思想都是一樣的。狀態轉移的時候可以從上一組轉移（選擇1個）與本組轉移（大於1個）。
狀態轉移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-cost[i][k]] + val[i][k],dp[i][j-cost[[\i][k]] + val[i][k]) (dp[i][j]表示選到i組填到容量j的最大價值，cost[i][k]表示第i組第k組的花費,val同上)
測試數據：
5 10000 3
1 4 6
2 5 7
3 4 99
1 55 77
2 44 66
3 10000 2
1 2 3
1 3 4
1 5 6
5 10000 3
1 1000 3
1 1000 4
2 100000 4
3 1000 3
3 1000 4
代碼：
[cpp]
#include <iostream>
#include <string.h>
using namespace std;
#define MAX 11000
struct node
{
int cos,val;
}arr[11][MAX];
int dp[11][MAX],len[11];
int max(int a,int b){
return a > b ? a : b;
}
int main()
{
int i,j,k,t,n,m;
int a,b,c,tot,ans,s;
while (scanf("%d%d%d",&n,&m,&k) != EOF){
memset(len,0,sizeof(len));
memset(dp,-1,sizeof(dp));
for (i = 1; i <= n; ++i){
scanf("%d%d%d",&a,&b,&c);
len[a]++;
arr[a][len[a]].cos = b;
arr[a][len[a]].val = c;
}
tot = dp[0][0] = 0;
for (i = 1; i <= k; ++i) {
if (!len[i]) break;
tot++;
for (j = 1; j <= len[i]; ++j)
for (s = m; s >= arr[i][j].cos; --s) {
if (dp[tot][s-arr[i][j].cos] != -1) {
int tp = dp[tot][s-arr[i][j].cos] + arr[i][j].val;
dp[tot][s] = max(dp[tot][s],tp);
}
if (dp[tot-1][s-arr[i][j].cos] != -1) {
int tp = dp[tot-1][s-arr[i][j].cos] + arr[i][j].val;
dp[tot][s] = max(dp[tot][s],tp);
}
}//for s
}//for i
for (ans = -1,i = m; i >= 0; --i)
if (ans < dp[tot][i]) ans = dp[tot][i];
if (tot == k && ans != -1) cout<<ans<<endl;
else cout<<"Impossible"<<endl;
}
}
摘自 ZeroClock
