HDU1712:ACboy needs your help(分组背包)

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1712

解释看这里:http://www.cnblogs.com/zhangmingcheng/p/3940332.html

这题之前竟然做过,竟然不记得了,做了一个小时,竟然没A,(我连分组背包干什么的都忘了)

这题的博客以前也写过,我重新写这篇博客,就是提醒自己一下。

代码:

#include <iostream>
using namespace std;
int a[101][101],f[101];
int main()
{
    int n,m,i,j,k;
    while(cin >> n >> m && (n != 0 || m != 0))
    {
        memset(f,0,sizeof(f));
        for(i = 1; i <= n; i++)
            for(j = 1; j <= m; j++)
                cin >> a[i][j];
        for(i = 1; i <= n; i++) //第一重循环:分组数
            for(j = m; j >= 0; j--) //第二重循环:容量体积
                for(k = 0; k <= j; k++) //第三重循环:属于i组的k
                    f[j] = max(f[j],f[j-k]+a[i][k]);
        cout << f[m] << endl;
    }
    return 0;
}
原文地址:https://www.cnblogs.com/zhangmingcheng/p/4381541.html