文档章节

动态规划---->0/1背包问题

小强斋太
 小强斋太
发布于 2016/11/09 20:05
字数 500
阅读 1
收藏 0
点赞 0
评论 0

0/1背包问题

有N件物品和一个容量为V的背包。第i件物品的重量是c[i],价值是w[i]。物品或者整件装入背包中, 或者根本不装入(即不能装入物品的一部分),求解将哪些物品装入背包可使价值总和最大。

最优性原理对0/1背包问题成立

算法基本思想

利用动态规划思想 ,子问题为:f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

其状态转移方程是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}   

解释一下上面的方程:“将前i件物品放入容量为v的背包中”这个子问题,如果只考虑第i件物品放或者不放,那么就可以转化为只涉及前i-1件物品的问题,即

1、如果不放第i件物品,则问题转化为“前i-1件物品放入容量为v的背包中”;

2、如果放第i件物品,则问题转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”(此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i])。

f[i][v]的值就是1、2中最大的那个值。

(注意:f[i][v]有意义当且仅当存在一个前i件物品的子集,其容量总和为v。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值。)

例子1:

C[v]从物品i=1开始,循环到物品3,期间,每次逆序得到容量v在前i件物品时可以得到的最大值。

例子2:

  <---------------------------------------------------------------

 

fori=1..N

   forv=V..0

        f[v]=max{f[v],f[v-c[i]]+w[i]};

0/1背包

© 著作权归作者所有

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
动态规划 &

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

Playboy002 ⋅ 2015/07/17 ⋅ 0

解决最优子结构问题的两种方法----动态规划和贪心算法

1、两种重要算法思想: 动态规划,贪心算法 2、动态规划: 基本原理:动态规划英文名dynamic programming。其中pogramming指的是表格法,而非编写计算机程序。因此,可以初步得出动态规划的基...

thoresa ⋅ 2015/05/18 ⋅ 0

贪心算法精讲

一.贪心算法的基本概念 当一个问题具有最优子结构性质时,我们会想到用动态规划法去解它。但有时会有更简单有效的算法。我们来看一个找硬币的例子。假设有四种硬币,它们的面值分别为二角五...

凡平 ⋅ 2011/10/09 ⋅ 0

白话版 动态规划法

关于动态规划法的解释, 大多都是基于背包问题的, 但背包问题背负了很多算法的解释工作,经常让初学者混淆,刚刚刷leetcode的时候,发现了一个很不错的关于动态规划算法的例题,特来分享一下! 这是...

木子昭 ⋅ 01/31 ⋅ 0

详解动态规划01背包问题--JavaScript实现

一开始在接触动态规划的时候,可能会云里雾里,似乎能理解思路,但是又无法准确地表述或者把代码写出来。本篇将一步一步通过作图的方式帮助初次接触动态规划的同学来理解问题。这一篇将以经典...

YinTokey ⋅ 05/19 ⋅ 0

XYNUOJ 1416: 竞赛总分

1416: 竞赛总分时间限制: 1 Sec 内存限制: 128 MB 提交: 12 解决: 11 [提交][状态][讨论版] 题目描述 学生在我们USACO的竞赛中的得分越多我们越高兴。 我们试着设计我们的竞赛以便人们能尽可...

dear_jia ⋅ 03/22 ⋅ 0

算法:Dynamic Programing

一、动态规划干嘛的 二、可以解决哪些问题 动态规划一般可分为:线性动规,区域动规,树形动规,背包动规四类。 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子...

猫咪要感冒 ⋅ 2016/10/09 ⋅ 0

动态规划之01背包问题(最易理解的讲解)

01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程 f[i,j]...

暖冰 ⋅ 2016/03/31 ⋅ 0

经典动态规划题若干

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,...

樂天 ⋅ 2016/01/22 ⋅ 0

动态规划之0-1背包问题

问题描述: 现 有n件物品和一个容量为c的背包。第i件物品的重量是重量为w[i],价值是v[i]。已知对于一件物品必须选择取(用1表示)或者不取(用0表示),且 每件物品只能被取一次(这就是“0...

一贱书生 ⋅ 2016/11/22 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

apollo配置中心的学习笔记

公司现在配置文件太多了,导致配置文件修改起来还是非常麻烦的。在boss(业务运营支撑系统)中,配置文件是存放在jar包的,通过应用jar包来引用配置文件(区分不同环境)。这种方式虽然能够满足...

miaojiangmin ⋅ 刚刚 ⋅ 0

Jena增删改查AP

插入、更新数据 public static void insert(){ String query = "PREFIX book: <http://www.book.com/jinyong/> \n" + " INSERT DATA \n" + ......

Vincent-Duan ⋅ 1分钟前 ⋅ 0

springMVC之与json数据交互方法

因为我也要返回json数据。所以需要这个注解@ResponseBody,把Java对象转换成json字符串 注意: 1、@RequestBody不能省,因为前台发过来的数据是json数据,得用这个注解去解析该怎么接收这些数...

颖伙虫 ⋅ 5分钟前 ⋅ 0

用实例域代替序号(31)

1、许多枚举天生就与一个单独的int 值相关联 ordinal 方法,返回枚举常量在类型中的数字位置 下述,枚举修改很不方便,不好维护 永远不要根据枚举的序数导出与他相关联的值 而是将他保存在一...

职业搬砖20年 ⋅ 7分钟前 ⋅ 0

并发编程---ConcurrentHashMap源码解析

ConcurrentHashMap是java中为了解决HashMap不能支持高并发而设计的新的实现。 ConcurrentHashMap的类结构 public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements C......

千古一梦888 ⋅ 10分钟前 ⋅ 0

微服务 WildFly Swarm 简介

我们将看到的最后一个Java微服务框架是一个相对较新的场景,它利用了 JBoss WildFly 应用服务器中已试过且受信任的 JavaEE 功能。WildFly Swarm 是 WildFly 应用服务器的一个完整的拆下来的组...

woshixin ⋅ 15分钟前 ⋅ 0

android apk 瘦身

头条APK瘦身之路 随着版本迭代,功能增加安装包体积也会慢慢增大。 今日头条576版本APK达到了25M,通过一系列的优化,到目前的607版本为12M。本文主要是介绍头条APK瘦身中用到的一些方法。 ...

GoldenVein ⋅ 18分钟前 ⋅ 1

mac机器学习开发环境部署及helloworld

一、下载并安装Anaconda2.7 https://repo.anaconda.com/archive/Anaconda2-5.2.0-MacOSX-x86_64.pkg 路径:/Users/shijun/anaconda2 二、运行Anaconda Navigator -> Environments -> base(ro......

八戒八戒八戒 ⋅ 29分钟前 ⋅ 0

关于日常开发的经验总结(Java),持续更新中

常量尽量使用枚举来表示,这样表现力会很强,因为枚举比一个常量类要有更多的扩展性 方法的入参和出参尽量不要使用Map,因为Map会让调用者感到迷惑,他不知道你里面装的什么,面向对象的开发...

小99 ⋅ 30分钟前 ⋅ 0

IDEA创建SpringMVC+Mybatis+Maven项目

视频如下(加载有点慢请见谅,服务器不太好): 视频

影狼 ⋅ 30分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部