動態規劃_分組揹包

鄭繼威

有N件物品和一個容量為V的揹包。第i件物品的重量是w，價值是c。
這些物品被劃分為若干組，每組中的物品互相衝突，最多選一件。
求解將哪些物品裝入揹包可使這些物品的重量總和不超過揹包容量，且價值總和最大。

Input
第一行：三個整數，v(揹包容量，v<=200),n（物品數量，n<=30)和t（最大組號，t<=10）;
第2…n+1行：每行三個整數wi,ci,p，表示每個物品的重量、價值、所屬組號。

Output
僅一行，一個數，表示最大總價值。
Sample Input
10 6 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3
Sample Output
20

1. #include<cstdio>
   
2. #include<iostream>
   
3. using namespace std;
   
4. int a[15][30],v[15][30],b[15],f[205],n,t,m,x,y,h;
   
5. int main()
   
6. {
   
7.         scanf("%d%d%d",&m,&n,&t);//背包可裝m公斤,有n件物品,物品分t組
   
8.         for (int i=1;i<=n;i++)
   
9.           {
   
10.                   scanf("%d%d%d",&x,&y,&h);//每件物品x公斤y元屬第h組
    
11.                   v[h][++b[h]]=x;//b用來存第h個組有多少件物品，v為代價
    
12.                   a[h][b[h]]=y;//a為價值
    
13.           }
    
14.         for (int i=1;i<=t;i++)//組
    
15.           for (int j=m;j>0;j--)//重量
    
16.             for (int k=1;k<=b[i];k++)//這個組的第幾件
    
17.               if (j>=v[i][k])//判斷是否越界
    
18.                 f[j]=max(f[j],f[j-v[i][k]]+a[i][k]);//動態轉移方程
    
19.         printf("%d",f[m]);
    
20.         system("pause");
    
21.         return 0;
    
22. }

複製代碼