文档章节

DP-01背包

梦想游戏人
 梦想游戏人
发布于 2016/09/17 15:49
字数 298
阅读 9
收藏 0

套路:最大值 , 最优,最大,最小,最长,计数

01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求最大价值

先暴力递归式求解

int w[10] = { 1, 4, 3, 0, 0, 0, 0, 0, 0 };
int v[10] = { 4, 6, 3, 0, 0, 0, 0, 0, 0 };


//0 5
int f(int x, int W)
{
	if (W < w[x])return f(x + 1, W);//剩余可用重量 小于当前物体重量

	if (W <= 0)return 0;//剩余重量 返回价值0
	if (x >= 4)return 0;

	int ret = max(f(x + 1, W - w[x]) + v[x], f(x + 1, W));// 拿和不拿

	return ret;
}

 

然后利用数组来存储已经计算过了的值,,递归到需要返回的时候

因为递归式的重量是依次递减,然后递推至最大

物品index 是在最大依次减小 所以DP循环的顺序就可以这样写

	for (int xx = num - 1; xx >= 0; xx--)
	{
		for (int ww = 0; ww <= MAX; ww++)
		{
			if (ww < w[xx])
			{
				arr[xx][ww] = arr[xx + 1][ww];
			}
			else
			{
				int a = arr[xx + 1][ww - w[xx]] + v[xx];//拿
				int b = arr[xx + 1][ww];// 不拿
				arr[xx][ww] = max(a, b);
			}
		}
	}

 

© 著作权归作者所有

下一篇: DP-N*M棋盘走法
梦想游戏人
粉丝 38
博文 445
码字总数 127977
作品 0
成都
私信 提问
动态规划 &

一、 动态规划(Dp问题):解决问题的关键点 1) 递推公式:(最有子结构) 2) 数据的初始化 用例分析: a. 01 背包的问题(Knapsack Problem) 定义: 一个背包的容量V; 存在N个物品:w[i...

Playboy002
2015/07/17
42
0
百练 4102 宠物小精灵之收服 【二维费用背包】

传送门 // 题意: 有k个怪物, 告诉每个怪物捕捉它需要的精灵球和皮卡丘收到的伤害, 给定精灵球的一共的数量和皮卡丘总的体力值, 问最多可以捕捉到多少个怪物, 然后如果能捕捉到的怪物相同则要...

anxdada
2018/03/08
0
0
2018年全国多校算法寒假训练营练习比赛(第二场)题解

A:栈模拟or字符串处理 题目链接:吐泡泡 思路:栈模拟,或者用string自带的函数进行处理,用string处理的时候要注意顺序从左到右!!! 字符串处理: #includeusing namespace std;int main...

ZscDst
2018/01/28
0
0
CCCC 题目集 L3 001 凑零钱 【背包 + 记录路径 + 思维】

传送门 // 题意: 给定n枚硬币的价值, 给出一个容量m, 问能否恰好在这n个中选择一些硬币使得其价值和加起来等于m, 并输出你选择的这些硬币的价值, 如果有多种选择, 输出字典序最小的那种. 思路...

anxdada
2018/03/10
0
0
洛谷 ~ P2014 ~ 选课 (树形背包)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/ZscDst/article/details/85002210 思路 树形背包的模板题。加一个虚拟的0结点然后选m+1个科目就OK。...

张松超
2018/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

阿里云POLARDB如何助力轻松筹打造5亿用户信赖的大病筹款平台?

轻松筹首创了“大病救助”模式,帮助了众多病患在第一时间解決了医疗资金等问题,为了从源头解决了医疗资金问题。而在轻松筹这样全球5.5亿用户信赖的大病筹款平台的背后,是日益增长的各种数...

阿里云云栖社区
12分钟前
3
0
Confluence 6 在升级过程中查看合并日志

为了监控升级的过程,你应该查看 application log 日志中的输出。 通常日志经常将会显示多个日志实例,这个实例是定义在日志的 INFO 级别的,通常格式如下: WikiToXhtmlMigrationThread-n -...

honeymoose
12分钟前
1
0
git diff 文件对比

git diff filepath 工作区与暂存区比较 git diff HEAD filepath 工作区与HEAD ( 当前工作分支) 比较 git diff --staged 或 --cached filepath 暂存区与HEAD比较 git diff branchName filepa......

李佳顺
13分钟前
1
0
spring mvc 定制化配置

spring mvc 自定义配置 1.实现某些接口,然后让上面的类加载进去. class MyHandlerMethodArgumentResolver implements HandlerMethodArgumentResolver { @Override public boolean......

最爱肉肉
15分钟前
1
0
OSG_采样像机的内容如果不显示到窗口上

cameraLight->setRenderTargetImplementation(Camera::FRAME_BUFFER_OBJECT);// 这句使内容不渲染到屏幕上cameraLight->setRenderOrder(Camera::PRE_RENDER); 1.setRenderTargetImplement......

洛克人杰洛
19分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部