HDU 1712 ACboy needs your help 多组背包
来源：http://acm.hdu.edu.cn/showproblem.php?pid=1712
题意：用m天的时间来学n门课程，给出n和m和一个num[n][m]的矩阵，num[n][m] 代表的是花m天的时间学习第n门课程所获得的价值，求最多能获得多大的价值
思路：将天数m作为背包的总体积，科目数目作为背包的种类数目，天数j作为背包的重量，num[i][j]作为背包的价值。由于一个科目只能选一次，即满足一组背包只能选一个，即转化为多组背包问题。
代码：
#include <iostream>#include <string.h>#include <cstdio>using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))const int N = 110;int num[N][N],dp[N];struct course{int val,weight;}cc[110];int main(){//freopen("1.txt","r",stdin);int numkind,totalweight;while(scanf("%d%d",&numkind,&totalweight) &&numkind&&totalweight){ CLR(num,0); int x; for(int i = 1;i <= numkind;++i){ for(int j = 1;j <= totalweight;++j){ scanf("%d",&num[i][j]); } } CLR(dp,0); for(int i = 1;i <= numkind;++i){ for(int w = totalweight;w > 0;--w){ for(int j = 0;j <= totalweight;++j){ if(w >= j) dp[w] = max(dp[w],dp[w - j] + num[i][j]); } } } int mmax = 0; for(int i = 0;i <= totalweight;++i) if(mmax < dp[i]) mmax = dp[i]; printf("%d\n",mmax);}return 0;}