背包九讲之分组背包－ＨＤＵ１７１２题解
- 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.
