文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 电脑基础知识 > 背包类动态规划小结---01背包
侵权投诉

背包类动态规划小结---01背包

背包类动态规划小结---01背包

背包类动态规划(资源类动态规划) ---01背包

CYXGRTX*

本文主要是针对本人学到的背包类dp进行总结(推荐:dd大犇的《背包九讲》,大部分知识都是从dd大神那学来的) 01背包

I: 概念

给你容量为V的背包和N件物品,每件物品放进背包中所占的容量和得到的价值都不同,第i件物品放进背包中需要w[i]的容量,但可以得到p[i]的价值,问放进去哪些物品可以得到最大的价值;

II: 思路

我们定义子问题为f[i][j],f[i][j]为前i件物品放进容量为j的背包中所得到的最大价值,对于第i件物品,我们只需要分析前i-1物品放进背包中的状态来确定第i件物品的策略。

策略只有两种(放or不放)。

F[i][j]=f[i-1,j];(第i件物品不放进背包中)

F[i][j]=f[i-1,j-w[i]]+p[i];(将第i件物品放进背包中)

由此,我们可以得到01背包的动态转移方程:

F[i][j]=max(f[i-1][j], f[i-1][j-w[i]]+p[i]);

而每一件物品为一个阶段i={1~n},j={0~v};

伪代码:

F[0, 0~V]=0;

For i=1~n;

For j=0~v;

F[i][j]=max(f[i-1][j], f[i-1][j-w[i]]+p[i]);

F[n][V]就是n件物品放进容量为V的背包中的最大值。

III:对于空间复杂度的优化

第一种方法:滚动数组

上面方法的时间复杂度为O(N*V),空间复杂度也为O(N*V),而且最终会有很多内存浪费掉,能不能重新使用浪费的内存,答案是可以的。我们只需要将p=1-p;p初始值为0;F[p][j]储存f[i-1][j],f[1-p][j]储存f[i][j],每一次我们只需要将 F[i-1][j]的位置储存当前状态。为什么?因为当前状态只有上一状态得到,与之前

第1页

你可能喜欢

热门文档

相关文档

  • 动态规划之01背包和完全背包

    动态规划之01背包和完全背包_IT/计算机_专业资料。分享0-1 背包 状态转移方程... 应届生求职季宝典 英文个人简历模板 创意简历模板汇集 推理型题分析与总结...

  • 01背包动态规划

    01背包动态规划_理学_高等教育_教育专区。01背包动态规划0-1 背包 1,首先建立背包类,包括重量属性 价值属性 以及相应的设置,获取函数 代码如下: public class ...

  • 01背包问题动态规划详解

    01背包问题动态规划详解_计算机软件及应用_IT/计算机_专业资料。01背包问题动态...小结 01 背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基...

  • 动态规划01背包问题代码

    动态规划01背包问题代码_计算机软件及应用_IT/...动态规划0/1背包问题问题描述:给定n种物品和一背包...教学总结精品范文 小学五年级英语教学工作总结 大学...

  • 利用动态规划解决01背包问题

    利用动态规划解决01背包问题_专业资料。龙源期刊网 http://www.qikan.com.cn 利用动态规划解决 01 背包问题 作者:孙宇兴 谭芬 来源:《现代交际》2010 年第 ...

  • 动态规划01背包问题

    动态规划01背包问题_计算机软件及应用_IT/计算机_专业资料。信息学竞赛动态规划 0/1 背包问题【0/1 背包问题】 在 0/1 背包问题中,需对容量为 c 的背包...

  • 01背包动态规划法

    01背包动态规划法_工学_高等教育_教育专区。01背包动态规划法0—1 背包问题 —一、实验目的 学习掌握动态规划法思想。 二、实验内容 用动态规划法求解 0—1 ...

  • 用动态规划法求解01背包问题

    用动态规划法求解 0/1 背包问题实验目的: 1、掌握动态规划算法求解问题的一般特征和步骤。 2、使用动态规划法编程,求解 0/1 背包问题。 实验要求: 1、掌握动态...

  • 01背包问题动态规划详解及C++代码

    01背包问题动态规划详解及C++代码_计算机软件及应用_IT/计算机_专业资料。0/1 背包问题动态规划详解及 C++代码 1. 问题描述 给定一个载重量为 C 的背包? n ...

  • NOIP 动态规划 背包问题-背包九讲

    小结 01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本...小结 显然,这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email