博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
动态规划:HDU1712-ACboy needs your help(分组背包问题)
阅读量:4843 次
发布时间:2019-06-11

本文共 1991 字,大约阅读时间需要 6 分钟。

ACboy needs your help

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 4   Accepted Submission(s) : 1
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
 
解题心得:
1、这还是第一次看分组背包问题,分组背包问题的一个要求就是,在很多组中,每次只能从一个组中选取一个数,然后从多组中得到最优解。这就和0-1背包问题、多重背包和完全背包问题不同了。三种基础的背包问题(0-1、多重、完全)其实可以看成一个组,是单组之中随便选取,求最优解。所以在遇到多组背包问题的时候要能够区分的出来。
2、因为多组背包问题相对于三种基础的背包问题来说多了一个条件——组数。所以要加一层循环,组数。
公式
for 所有的组k    for v = V...0        for 所有i组的k            f[v]=max{f[v],f[v-c[i]]+w[i]}
要注意一点,三层循环之中容量必须放在第二层之中,否则就变成了0-1背包问题了
/*之前在做这个题的时候看了一个人的博客,他把公式给写反了,v...V写到内层去了,弄得一直WA,也是无语了,在这个博客里面纠正一下这个错误*/#include
using namespace std;const int maxn = 1e5+100;const int maxn2 = 1e2+10;int maps[maxn2][maxn2];int dp[maxn];struct NUM{ int va,cost;}num[maxn];int main(){ int n,m; while(scanf("%d%d",&n,&m) && n+m) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&maps[i][j]); for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) for(int k=1;k<=j;k++) dp[j] = max(dp[j],dp[j-k]+maps[i][k]); printf("%d\n",dp[m]); }}

转载于:https://www.cnblogs.com/GoldenFingers/p/9107331.html

你可能感兴趣的文章
不能在DropDownList 中选择多个项
查看>>
【Unity渲染】Camera RenderToCubemap 渲染到立方体纹理
查看>>
n2n网络穿透内网
查看>>
让“懒惰” Linux 运维工程师事半功倍的 10 个关键技巧!
查看>>
写给自己看的小设计4 - 对象设计通用原则之扩展原则
查看>>
oem 重建
查看>>
LNMP之Nginx
查看>>
构造函数中的异常处理(转)
查看>>
SI Macro
查看>>
jquery动态调整div大小使其宽度始终为浏览器宽度
查看>>
这篇文章主要为大家详细介绍了jQuery密码强度验证控件使用详解的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...
查看>>
寒假作业
查看>>
iframe内联网页的应用
查看>>
android 开发 View _13 绘制图片与BitmapShader位图的图像渲染器
查看>>
[bzoj2131]免费的馅饼 树状数组优化dp
查看>>
CreateMutex()参数报错问题
查看>>
Linux三剑客-常用命令
查看>>
Excel的列数以数字格式查看
查看>>
unity 2d 和 NGUI layer
查看>>
Sublime Text shift+ctrl妙用、Sublime Text快捷组合键大全
查看>>