hdu1712 分组背包

时间:2021-12-23 22:48:43

题目链接: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 分组背包的更多相关文章

  1. hdu1712 分组背包 ACboy needs your help

    ACboy needs your help Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Ot ...

  2. 分组背包模板题 hdu1712

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1712 第一次接触分组背包,参考博客:https://blog.csdn.net/yu121380/ar ...

  3. P1757 通天之分组背包 &sol; hdu1712 ACboy needs your help (分组背包入门)

    P1757 通天之分组背包 hdu1712 ACboy needs your help hdu1712题意:A[i][j]表示用j天学习第i个课程能够得到A[i][j]的收益,求m天内获得的收益最大值 ...

  4. hdu1712 ACboy needs your help 分组背包

    最基础的分组背包~ #include <iostream> #include <cstdio> #include <cstdlib> #include <cs ...

  5. HDU1712简单的分组背包

    HDU1712http://acm.hdu.edu.cn/showproblem.php?pid=1712 简单的分组背包 #include <map> #include <set& ...

  6. 【HDU1712】ACboy needs your help(分组背包)

    将背包九讲往后看了看,学习了一下分组背包.来做几道入门题,试试手. #include <iostream> #include <cstring> #include <cs ...

  7. HDU1712&colon;ACboy needs your help&lpar;分组背包模板)

    http://acm.hdu.edu.cn/showproblem.php?pid=1712 Problem Description ACboy has N courses this term, an ...

  8. dp之分组背包hdu1712

    题意:有n门课程,和m天时间,完成a[i][j]得到的价值为第i行j列的数字,求最大价值...... 思路:分组背包,就是第n门课程,可以做一天,可以做两天,但它们相斥,你做了一天,就不能再做一天.. ...

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

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=1712 解释看这里:http://www.cnblogs.com/zhangmingcheng/p/3940 ...

随机推荐

  1. Coursera台大机器学习课程笔记7 -- Noise and Error

    本章重点:  简单的论证了即使有Noise,机器依然可以学习,VC Dimension对泛化依然起作用:介绍了一些评价Model效果的Error Measurement方法. 一论证即使有Noisy, ...

  2. abrt-hook-ccpp&colon; Saved core dump of pid 12224导致dn挂掉问题

    一.引言: 最近发现datanode老是无缘无故的进程挂掉,从程序的日志没有stop迹象,只能从/var/log/messages入手,发现如下信息: 从namenode的页面也可以看到进程消息的时间 ...

  3. RSA客户端js加密服务器C&num;解密&lpar;含源码&rpar;

    国内私募机构九鼎控股打造APP,来就送 20元现金领取地址:http://jdb.jiudingcapital.com/phone.html内部邀请码:C8E245J (不写邀请码,没有现金送)国内私 ...

  4. linux服务端的网络编程

    常见的Linux服务端的开发模型有多进程.多线程和IO复用,即select.poll和epoll三种方式,其中现在广泛使用的IO模型主要epoll,关于该模型的性能相较于select和poll要好不少 ...

  5. ORACLE的执行计划

    转自:http://www.cnblogs.com/lovingprince/archive/2007/12/07/2166400.html 背景知识:        为了更好的进行下面的内容我们必须 ...

  6. iOS MVVM 参考

    实践干货!猿题库 iOS 客户端架构设计 ReactiveCocoa入门教程 ReactiveCocoa入门教程——第二部 谈谈MVVM和MVC,使用swift集成RFP框架(ReactiveCoco ...

  7. Lua脚本在redis分布式锁场景的运用

    目录 锁和分布式锁 锁是什么? 为什么需要锁? Java中的锁 分布式锁 redis 如何实现加锁 锁超时 retry redis 如何释放锁 不该释放的锁 通过Lua脚本实现锁释放 用redis做分 ...

  8. 异常:unity3d ArgumentException&colon; The Assembly System&period;Configuration is referenced by System&period;Data&period;

    异常:ArgumentException: The Assembly System.Configuration is referenced by System.Data. But the dll is ...

  9. 020 Spark中分组后的TopN,以及Spark的优化(重点)

    一:准备 1.源数据 2.上传数据 二:TopN程序编码 1.程序 package com.ibeifeng.bigdata.spark.core import java.util.concurren ...

  10. &lt&semi;spark&gt&semi; hadoop&sol;spark 集群搭建

    参考的这3个文档,虽然搭建花了挺长时间也遇到挺多问题,但是这3个文档对我的帮助确实挺大,如果有兴趣的或者有需要的可以参考以下文档. http://blog.csdn.net/wy250229163/a ...