题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1712
题意:有n门课程,和m天时间,完成mp[i][j]得到的价值为第i行j列的数字,求最大价值。
思路:分组背包。
分组背包:
问题
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
算法
这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,则有:
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]}
注意这里的三层循环的顺序,“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
AC代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std; int mp[][];
int dp[]; int N,M; int main()
{
while(cin>>N>>M && (N+M))
{
for(int i=; i<=N; i++)
for(int j=; j<=M; j++)
cin>>mp[i][j];
memset(dp,,sizeof(dp));
for(int i=; i<=N; i++)
for(int j=M; j>=; j--)
for(int k=; k<=M; k++)
if(j>=k) dp[j]=max(dp[j],dp[j-k]+mp[i][k]);
cout<<dp[M]<<endl;
}
return ;
}
hdu1712 分组背包的更多相关文章
-
hdu1712 分组背包 ACboy needs your help
ACboy needs your help Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot ...
-
分组背包模板题 hdu1712
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1712 第一次接触分组背包,参考博客:https://blog.csdn.net/yu121380/ar ...
-
P1757 通天之分组背包 / hdu1712 ACboy needs your help (分组背包入门)
P1757 通天之分组背包 hdu1712 ACboy needs your help hdu1712题意:A[i][j]表示用j天学习第i个课程能够得到A[i][j]的收益,求m天内获得的收益最大值 ...
-
hdu1712 ACboy needs your help 分组背包
最基础的分组背包~ #include <iostream> #include <cstdio> #include <cstdlib> #include <cs ...
-
HDU1712简单的分组背包
HDU1712http://acm.hdu.edu.cn/showproblem.php?pid=1712 简单的分组背包 #include <map> #include <set& ...
-
【HDU1712】ACboy needs your help(分组背包)
将背包九讲往后看了看,学习了一下分组背包.来做几道入门题,试试手. #include <iostream> #include <cstring> #include <cs ...
-
HDU1712:ACboy needs your help(分组背包模板)
http://acm.hdu.edu.cn/showproblem.php?pid=1712 Problem Description ACboy has N courses this term, an ...
-
dp之分组背包hdu1712
题意:有n门课程,和m天时间,完成a[i][j]得到的价值为第i行j列的数字,求最大价值...... 思路:分组背包,就是第n门课程,可以做一天,可以做两天,但它们相斥,你做了一天,就不能再做一天.. ...
-
HDU1712:ACboy needs your help(分组背包)
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1712 解释看这里:http://www.cnblogs.com/zhangmingcheng/p/3940 ...
随机推荐
-
Coursera台大机器学习课程笔记7 -- Noise and Error
本章重点: 简单的论证了即使有Noise,机器依然可以学习,VC Dimension对泛化依然起作用:介绍了一些评价Model效果的Error Measurement方法. 一论证即使有Noisy, ...
-
abrt-hook-ccpp: Saved core dump of pid 12224导致dn挂掉问题
一.引言: 最近发现datanode老是无缘无故的进程挂掉,从程序的日志没有stop迹象,只能从/var/log/messages入手,发现如下信息: 从namenode的页面也可以看到进程消息的时间 ...
-
RSA客户端js加密服务器C#解密(含源码)
国内私募机构九鼎控股打造APP,来就送 20元现金领取地址:http://jdb.jiudingcapital.com/phone.html内部邀请码:C8E245J (不写邀请码,没有现金送)国内私 ...
-
linux服务端的网络编程
常见的Linux服务端的开发模型有多进程.多线程和IO复用,即select.poll和epoll三种方式,其中现在广泛使用的IO模型主要epoll,关于该模型的性能相较于select和poll要好不少 ...
-
ORACLE的执行计划
转自:http://www.cnblogs.com/lovingprince/archive/2007/12/07/2166400.html 背景知识: 为了更好的进行下面的内容我们必须 ...
-
iOS MVVM 参考
实践干货!猿题库 iOS 客户端架构设计 ReactiveCocoa入门教程 ReactiveCocoa入门教程——第二部 谈谈MVVM和MVC,使用swift集成RFP框架(ReactiveCoco ...
-
Lua脚本在redis分布式锁场景的运用
目录 锁和分布式锁 锁是什么? 为什么需要锁? Java中的锁 分布式锁 redis 如何实现加锁 锁超时 retry redis 如何释放锁 不该释放的锁 通过Lua脚本实现锁释放 用redis做分 ...
-
异常:unity3d ArgumentException: The Assembly System.Configuration is referenced by System.Data.
异常:ArgumentException: The Assembly System.Configuration is referenced by System.Data. But the dll is ...
-
020 Spark中分组后的TopN,以及Spark的优化(重点)
一:准备 1.源数据 2.上传数据 二:TopN程序编码 1.程序 package com.ibeifeng.bigdata.spark.core import java.util.concurren ...
-
<;spark>; hadoop/spark 集群搭建
参考的这3个文档,虽然搭建花了挺长时间也遇到挺多问题,但是这3个文档对我的帮助确实挺大,如果有兴趣的或者有需要的可以参考以下文档. http://blog.csdn.net/wy250229163/a ...