題記

一個旅行者有一個最多能裝V公斤的背包和有N件物品，它們的重量分別是W[1]，W[2]，…,W[n]，它們的價值分別為C[1],C[2],…,C[n]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

算法

這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有$$f[k][v]=maxf[k?1][v],f[k?1][v?w[i]]+c[i]（物品i屬于第k組）$$
使用一維數組的偽代碼如下：

for 所有的組 kfor v=V..0for 所有的 i 屬于組 kf[v]=max(f[v],f[v-w[i]]+c[i])

題目

1272：【例9.16】分組背包
【題目描述】
一個旅行者有一個最多能裝V公斤的背包，現在有n件物品，它們的重量分別是W1，W2，…,Wn，它們的價值分別為C1,C2,…,Cn。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

【輸入】
第一行：三個整數，V(背包容量，V≤200)，N(物品數量，N≤30)和T(最大組號，T≤10)；

第2…N+1行：每行三個整數Wi,Ci,P，表示每個物品的重量，價值，所屬組號。

【輸出】
僅一行，一個數，表示最大總價值。

【輸入樣例】

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

【輸出樣例】

20

代碼

#include<bits/stdc++.h>
using namespace std;
int n,v,t;
int w[310],c[310],a[310][310],f[310];
//a[p][0]數組記錄每組有多少物品 
int main() {cin>>v>>n>>t;for(int i=1; i<=n; i++) {int p;cin>>w[i]>>c[i]>>p;a[p][++a[p][0]]=i; }for(int p=1; p<=t; p++)for(int j=v; j>=0; j--)for(int i=1; i<=a[p][0]; i++)//循環每一組數據中的物品 if(j>=w[a[p][i]])//保證數組不會越界 f[j]=max(f[j],f[j-w[a[p][i]]]+c[a[p][i]]);//計算最大價值 cout<<f[v];//輸出在v公斤時的最大價值 return 0;
}