背包九讲之分组背包-HDU1712题解

以杭电1712为例子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”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。

杭电1712

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],问如何安排收益最大。

用数据

22

21

21

来分析根据背包九讲中p06的思路就是三层for

第一层表示每一个类别找一边,第二个for表示每一个背包容量从大到小找一遍,第三个for表示

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("%d\n",f[c] );
}
测试请看如下
N = 2 c = 2
A[][] i 1 2
j       0 0   
1       2 1
2       2 1
i = 1 : 第一个for
f[j] = max(f[j],f[j-k]+A[i][k]);
f[] k 1 2   在k变化的情况下,看看f[j]从2-1的变化,
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("%d\n",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

本文链接地址: 背包九讲之分组背包-HDU1712题解

No related posts.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励