# 背包九讲之分组背包－ＨＤＵ１７１２题解

### 则

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]}

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

２２

２１

２１

```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 : 第一个ｆｏｒ
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("%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();
}
}```

No related posts.

178 篇文章22 人订阅

0 条评论