背包九講之分組背包－ＨＤＵ１７１２題解
- 2019 年 11 月 29 日
- 筆記
以杭電１７１２為例子http://acm.hdu.edu.cn/showproblem.php?pid=1712
問題
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相衝突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
則
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有：
f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬於第k組}
使用一維數組的偽程式碼如下：
for 所有的組k
for v=V..0
for 所有的i屬於組k
f[v]=max{f[v],f[v-c[i]]+w[i]}
注意這裡的三層循環的順序，甚至在本文的beta版中我自己都寫錯了。「for v=V..0」這一層循環必須在「for 所有的i屬於組k」之外。這樣才能保證每一組內的物品最多只有一個會被添加到背包中。
杭電１７１２
Problem Description
ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has. Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j]. N = 0 and M = 0 ends the input.
Output
For each data set, your program should output a line which contains the number of the max profit ACboy will gain.
Sample Input
2 2
1 2
1 3
2 2
2 1
2 1
2 3
3 2 1
3 2 1
0 0
Sample Output
3
4
6
題目大意：n個課程，最多有m天可以用，每個課程花費不同的天數得到的收益不同，第i個課程花費j天來學那麼收益為a[i][j]，問如何安排收益最大。
用數據
２２
２１
２１
來分析根據背包九講中ｐ０６的思路就是三層ｆｏｒ
第一層表示每一個類別找一邊，第二個ｆｏｒ表示每一個背包容量從大到小找一遍，第三個ｆｏｒ表示
void fenzubeibao() { memset(f,0,sizeof(f)); int i,j,k; for (i = 1; i <= n; i++) { for ( j = c; j >= 0; j--) { for (k = 1; k <= j; k++){ f[j] = max(f[j],f[j-k]+A[i][k]); } } } printf("%dn",f[c] ); } 測試請看如下 N = 2 c = 2 A[][] i 1 2 j 0 0 1 2 1 2 2 1 i = 1 : 第一個ｆｏｒ f[j] = max(f[j],f[j-k]+A[i][k]); f[] k 1 2 在ｋ變化的情況下，看看ｆ［ｊ］從２－１的變化， j 0 0 0 2 2 1 1 2 1 i = 2 f[] k 1 2 j 0 0 0 2 4 1 1 2 1
源程式碼如下：
#include <stdio.h> #include <string.h> #define max(a,b) a>b?a:b int A[105][105],f[1001]={0}; int n,c,k; void fenzubeibao() { memset(f,0,sizeof(f)); int i,j,k; for (i = 1; i <= n; i++) { for ( j = c; j >= 0; j--) { for (k = 1; k <= j; k++){ f[j] = max(f[j],f[j-k]+A[i][k]); } } } printf("%dn",f[c] ); } int main() { while(~scanf("%d%d",&n,&c))//n個物體，c的容量 { int i,j; for(i = 1 ; i <= n; i++) { for(j = 1; j <= c; j++) { scanf("%d",&A[i][j]); } } fenzubeibao(); } }
原創文章，轉載請註明： 轉載自URl-team
本文鏈接地址: 背包九講之分組背包－ＨＤＵ１７１２題解
No related posts.
