程序员人生网站导航

HDU 1712 ACboy needs your help(分组背包)

栏目：互联网时间：2014-11-11 08:13:26

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

题意:

小杰有m天的时间去上n门不同的课. 对第i门课来讲, 如果小杰花j天的时间在该课上, 那末小杰可以取得val[i][j]的价值. 现在给出矩阵val[n][m], 要你求出小杰能取得的最大价值和?

分析:

咋1看, n门课, m天的时间, 要我们求最大价值. 那末明显是从n门课当选出适合的几门, 是的总花费的时间<=m的条件下, 价值最大化. 但是发现每门课有m种不同的价值获得方式.

所以我们换1种问题描写方式: 有n组物品, 每组物品有m个且每组物品中最多只能选1个物品. 第i组物品的花费分别为1 2 3 …m, 第i组物品的价值分别为val[i][1], val[i][2]…val[i][m]. 现在问你初始金钱为m时, 通过上面n组物品, 最多能取得多少价值的物品?

上面问题就是1个明显的分组背包问题了. 我们令dp[i][j]==x表示只选前i组物品且总花费<=j时, 能取得的最大价值为x.

初始化: dp全为0.

状态转移: dp[i][j] == max( dp[i⑴][j] , dp[i⑴][j-cost[k]]+val[k])

其中cost[k]和val[k]指的是第i组物品的第k个物品的花费和价值.

上面公式前者表示第i组物品1个都不选, 后者表示第i组物品选1个.

终究所求: dp[n][m]的值.

注意: dp递推的3层循环的相互顺序不能改变, 否者会错.(可以自己想想为何是这样的循环顺序).程序用的转动数组, dp只有1维.

AC代码:

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=100+5; int n;//n组物品 int m;//初始金钱数和每组中物品数目 int cost[maxn][maxn]; int val[maxn][maxn]; int dp[maxn]; int main() { while(scanf("%d%d",&n,&m)==2 && n) { //读取输入 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&val[i][j]); cost[i][j]=j; } //递推进程 memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++)//第i组 for(int j=m;j>=0;j--)//<=j花费时 for(int k=1;k<=m;k++)//第i组的第k个物品 { if(j>=cost[i][k]) dp[j] = max(dp[j], dp[j-cost[i][k]]+val[i][k]); } //输出结果 printf("%d ",dp[m]); } return 0; }

------分隔线----------------------------

上一篇 【十四】注入框架RoboGuice使用总结

下一篇 Webx框架：依赖注入

------分隔线----------------------------