文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:05
字数 500
阅读 1
收藏 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背包

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/14/5637095.html

共有 人打赏支持
下一篇: 位图索引
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
前端与算法-动态规划之01背包问题浅析与实现

去年因为工作中的某个应用场景,需要使用到动态规划,为此花了些时间啃了啃背包算法 为啥去年的东西,今年才写粗来,也许大概是懒吧 动态规划 Dynamic Programming 先简单说下什么是动态规划...

小黎也
2018/07/31
0
0
动态规划 &

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

Playboy002
2015/07/17
42
0
js算法初窥05(算法模式02-动态规划与贪心算法)

  在前面的文章中(js算法初窥02(排序算法02-归并、快速以及堆排)我们学习了如何用分治法来实现归并排序,那么动态规划跟分治法有点类似,但是分治法是把问题分解成互相独立的子问题,最...

zaking
2018/05/29
0
0
解决最优子结构问题的两种方法----动态规划和贪心算法

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

thoresa
2015/05/18
0
0
详解动态规划01背包问题--JavaScript实现

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

YinTokey
2018/05/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何从复杂单体应用快速迁移到微服务?

想必你已知道了微服务及其工作原理,现在是时候探讨如向微服务转变这个关键话题了。 为什么要向微服务转变 整体式(monolithic)应用程序很庞大(代码行数方面)、很复杂(功能依赖和数据等方...

架构师springboot
12分钟前
0
0
Maven与打包方式总结

一. war包 一般都是直接打成war包即可, 相关依赖都会放到 WEB-INF/lib 下. <plugin> <artifactId>maven-war-plugin</artifactId> <configuration> <version>3.0</version>......

foreach
14分钟前
0
0
JDBC详解

一、相关概念 1.什么是JDBC   JDBC(Java Data Base Connectivity,java数据库连接)是一种用于执行SQL语句的Java API,可以为多种关系数据库提供统一访问,它由一组用Java语言编写的类和接...

木云凌
37分钟前
0
0
分布式之延时任务方案解析

方案分析 (1)数据库轮询 思路 该方案通常是在小型项目中使用,即通过一个线程定时的去扫描数据库,通过订单时间来判断是否有超时的订单,然后进行update或delete等操作 实现 博主当年早期是用...

微笑向暖wx
40分钟前
1
0
博客目录

1.剑指offer目录 剑指offer目录 2.开放的面试题 开放面试题目录

细节探索者
40分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部