文档章节

动态规划---->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 先简单说下什么是动态规划...

小黎也
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
05/29
0
0
解决最优子结构问题的两种方法----动态规划和贪心算法

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

thoresa
2015/05/18
0
0
白话版 动态规划法

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

木子昭
01/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java基础知识,小栗子

来操作一下数组.....注意带参数的变长数组的使用. package com.avatus;import java.util.Random;import java.util.Scanner;public class Main { public static void main(St...

Oh_really
14分钟前
0
0
SSO单点登录PHP简单版

  前面做了一个新项目,需要用户资源可以需要共享。由于之前没有做过这样的东西,回家之后,立马网站百度“单点登录”。帖子很多,甄别之后,这里列几篇认为比较有营养。   http://blog...

slagga
51分钟前
2
0
Java 泛型详解-绝对是对泛型方法讲解最详细的,没有之一

对java的泛型特性的了解仅限于表面的浅浅一层,直到在学习设计模式时发现有不了解的用法,才想起详细的记录一下。 本文参考java 泛型详解、Java中的泛型方法、 java泛型详解 1 概述 泛型在j...

hensemlee
55分钟前
2
0
Annotation注解详细介绍

目录介绍 1.Annotation库的简单介绍 2.@Nullable和@NonNull 3.资源类型注释 4.类型定义注释 5.线程注释 6.RGB颜色纸注释 7.值范围注释 8.权限注释 9.重写函数注释 10.返回值注释 11.@Keep注释...

潇湘剑雨
57分钟前
2
0
一步步编写自己的PHP爬取代理IP项目(二)

这一章节我们正式开展我们的爬虫项目,首先我们先要知道哪个网站能获取到免费代理IP,目前比较火的有西刺代理,快代理等,这里我们拿西刺代理作为例子。 这里就是一个个免费的IP地址以及各自...

NateHuang
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部