关于背包问题的一些理解和应用

1.背包问题介绍

背包问题不单单是一个简单的算法问题,它本质上代表了一大类问题,这类问题实际上是01线性规划问题,其约束条件和目标函数如下:

自从dd_engi在2007年推出《背包问题九讲》之后,背包问题的主要精髓基本已道尽。本文没有尝试对背包问题的本质进行扩展或深入挖掘,而只是从有限的理解(这里指对《背包问题九讲》的理解)出发,帮助读者更快地学习《背包问题九讲》中的提到的各种背包问题的主要算法思想,并通过实例解释了相应的算法,同时给出了几个背包问题的经典应用。

2.背包问题及应用

dd_engi在《背包问题九讲》中主要提到四种背包问题,分别为:01背包问题,完全背包问题,多重背包问题,二维费用背包问题。本节总结了这几种背包问题,并给出了其典型的应用以帮助读者理解这几种问题的本质。

2.101背包问题

(1)问题描述

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

(2)状态转移方程

其中,f(i,v) 表示从前i件物品选择若干物品装到容量为v的背包中产生的最大价值。当v=0时,f(i,v)初始化为0,表示题目不要求背包一定刚好装满,而f(i,v)=inf/-inf(正无穷或负无穷)表示题目要求背包一定要刚好装满。下面几种背包类似,以后不再赘述。

(3) 伪代码

从转移方程上可以看出,前i个物品的最优解只依赖于前i-1个物品最优解,而与前i-2,i-3,…各物品最优无直接关系,可以利用这个特点优化存储空间,即只申请一个一维数组即可,算法时间复杂度(O(VN))为:

for i=1..N
 
  for v=V..0
 
    f[v]=max{f[v],f[v-c[i]]+w[i]};

注意v的遍历顺序!!!

下面几种背包用到类似优化,以后不再赘述。

(4) 举例

V=10,N=3,c[]={3,4,5}, w={4,5,6}

(1)背包不一定装满

计算顺序是:从右往左,自上而下:

(2)背包刚好装满

计算顺序是:从右往左,自上而下。注意初始值,其中-inf表示负无穷

(5) 经典题型

[1] 你有一堆石头质量分别为W1,W2,W3…WN.(W<=100000,N <30)现在需要你将石头合并为两堆,使两堆质量的差为最小。

[2] 给一个整数的集合,要把它分成两个集合,要两个集合的数的和最接近

[3] 有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0小于n≤30),每个物品有一个体积(正整数)。要求从n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

2.2完全背包问题

(1)问题描述

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

(2)状态转移方程

或者:

(3) 伪代码

for i=1..N
 
  for v=0..V
 
    f[v]=max{f[v],f[v-c[i]]+w[i]};

注意v的遍历顺序!!!

注意,时间复杂度仍为:O(VN).

(4) 举例

V=10,N=3,c[]={3,4,5}, w={4,5,6}

(1)背包不一定装满

计算顺序是:从左往右,自上而下:

(2)背包刚好装满

计算顺序是:从左往右,自上而下。注意初始值,其中-inf表示负无穷

(5) 经典题型

[1] 找零钱问题:有n种面额的硬币,每种硬币无限多,至少用多少枚硬币表示给定的面值M?

2.3多重背包问题

(1)问题描述

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

(2)状态转移方程

(3) 解题思想

用以下方法转化为普通01背包问题:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,…,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种 物品分成系数分别为1,2,4,6的四件物品。这种方法能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示。这个很容易证明,证明过程中用到以下定理:任何一个整数n均可以表示成:n=a0*2^0+a1*2^1+…+ak*2^k,其中ak=0或者1(实际上就是n的二进制分解),

定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

该定理的证明如下:

(1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

(2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

(3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

(证毕!)

该算法的时间复杂度为:O(V*sum(logn[i])).

(4) 经典题型

[1] 找零钱问题:有n种面额的硬币,分别为a[0], a[1],…, a[n-1],每种硬币的个数为b[0], b[1],…, b[n-1],至少用多少枚硬币表示给定的面值M?

2.4二维费用背包

(1)问题描述

二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问 怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种 背包容量)分别为V和U。物品的价值为w[i]。

(2)状态转移方程

(3)算法思想

采用同一维情况类似的方法求解

(4)经典题型

有2n个整数,平均分成两组,每组n个数,使这两组数的和最接近。

3.背包总结

背包问题实际上代表的是线性规划问题,一般要考虑以下几个因素已决定选取什么样的算法:

(1)约束条件,有一个还是两个或者更多个,如果是一个,可能是01背包,完全背包或者多重背包问题,如果有两个约束条件,则可能是二维背包问题。

(2)优化目标,求最大值,还是最小值,还是总数(只需将max换成sum)

(3)每种物品的个数限制,如果每种物品只有一个,只是简单的01背包问题,如果个数无限制,则是完全背包问题,如果每种物品的个数有限制,则是多重背包问题。

(4)背包是否要求刚好塞满,注意不塞满和塞满两种情况下初始值不同。

4.参考资料

dd_engi:《背包问题九讲》

(0)

相关推荐

  • PHP贪婪算法解决0-1背包问题实例分析

    本文实例讲述了PHP贪婪算法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 贪心算法解决0-1背包问题,全局最优解通过局部最优解来获得!比动态规划解决背包问题更灵活! //0-1背包贪心算法问题 class tanxin{ public $weight; public $price; public function __construct($weight=0,$price=0) { $this->weight=$weight; $this->price=$price; } }

  • C#使用回溯法解决背包问题实例分析

    本文实例讲述了C#使用回溯法解决背包问题的方法.分享给大家供大家参考.具体如下: 背包问题描述: 给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高 实现代码: using System; using System.Collections.Generic; using System.Text; namespace BackRack { //要装入书包的货物节点 class BagNode { public int mark;//货物编号,从0开始

  • PHP回溯法解决0-1背包问题实例分析

    本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna

  • C#用递归算法解决经典背包问题

    1.引子 我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,用脑子才行,下面就教您如何解决这样的问题,以获得更多的奖品. 2.应用场景 在一个物品向量中找到一个子集满足条件如下 : 1)这个子集加起来的体积大小不能大于指定阀值 2)这个物品子集加起来价值大小是向量V中所有满足条件1的子集中最大的 3.分析 背包问题有好多版本,本文只研究0/1版本,即对一个物体要么选用,要么就抛弃,不能将一个

  • 用贪心法求解背包问题的解决方法

    贪心方法:总是对当前的问题作最好的选择,也就是局部寻优.最后得到整体最优.应用:1:该问题可以通过"局部寻优"逐步过渡到"整体最优",这是贪心选择性质与"动态规划"的主要差别.2:最优子结构性质:某个问题的整体最优解包含了"子"问题的最优解.完整的代码如下: 复制代码 代码如下: #include "iostream"using namespace std;struct goodinfo{ float p;

  • PHP动态规划解决0-1背包问题实例分析

    本文实例分析了PHP动态规划解决0-1背包问题.分享给大家供大家参考.具体分析如下: 背包问题描述:一个承受最大重量为W的背包,现在有n个物品,每个物品重量为t, 每个物品的价值为v. 要使得这个背包重量最大(但不能超过W),同时又需要背包的价值最大. 思路:定义一个二维数组,一维为物品数量(表示每个物品),二维是重量(不超过最大,这里是15),下面数组a, 动态规划原理思想,max(opt(i-1,w),wi+opt(i-1,w-wi)) 当中最大值, opt(i-1,w-wi)指上一个最优解

  • C++动态规划之背包问题解决方法

    本文实例讲述了C++动态规划之背包问题解决方法.分享给大家供大家参考.具体分析如下: 问题描述: 背包的最大容量为W,有N件物品,每件物品重量为w,价值为p,怎样选择物品能使得背包里的物品价值最大? 输入: 10 3   (W,N) 4 5   (w,p) 6 7   (w,p) 8 9   (w,p) 实现代码: #include <stdio.h> #define THING 20 #define WEIGHT 100 int arr[THING][WEIGHT]; /* 背包容量为wei

  • C#使用动态规划解决0-1背包问题实例分析

    本文实例讲述了C#使用动态规划解决0-1背包问题的方法.分享给大家供大家参考.具体如下: // 利用动态规划解决0-1背包问题 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Knapsack_problem // 背包问题关键在于计算不超过背包的总容量的最大价值 { class Program { static void Main() { int i;

  • 关于背包问题的一些理解和应用

    1.背包问题介绍 背包问题不单单是一个简单的算法问题,它本质上代表了一大类问题,这类问题实际上是01线性规划问题,其约束条件和目标函数如下: 自从dd_engi在2007年推出<背包问题九讲>之后,背包问题的主要精髓基本已道尽.本文没有尝试对背包问题的本质进行扩展或深入挖掘,而只是从有限的理解(这里指对<背包问题九讲>的理解)出发,帮助读者更快地学习<背包问题九讲>中的提到的各种背包问题的主要算法思想,并通过实例解释了相应的算法,同时给出了几个背包问题的经典应用. 2.

  • C语言数学问题与简单DP背包问题详解

    目录 数学 买不到的数目 蚂蚁感冒 饮料换购 简单DP 背包问题 二维 一维 数学 顾名思义,数学类的题就是都可以用数学知识求解. 买不到的数目 这是第四届蓝桥杯省赛C++A组,第四届蓝桥杯省赛JAVAC组的一道题 小明开了一家糖果店. 他别出心裁:把水果糖包成4颗一包和7颗一包的两种. 糖果不能拆包卖. 小朋友来买糖的时候,他就用这两种包装来组合. 当然有些糖果数目是无法组合出来的,比如要买 10 颗糖. 你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17. 大于17的任何数字

  • C语言动态规划多种背包问题分析讲解

    目录 写在前面 01背包问题 完全背包问题 多重背包问题 I 多重背包问题 II 为什么可以这样优化呢 一 .二进制与十进制 二 .动态规划的时间复杂度估算 三 .多重背包 分组背包问题 写在前面 之前讲过简单DP,经典01背包问题,在这我将会把背包问题更深入的讲解,希望能帮助大家更好的理解. 01背包问题 C语言数学问题与简单DP01背包问题详解 先回忆一下这个图 在这我再将01背包问题代码发一遍,可以用来做对比. 二维: #include<bits/stdc++.h> using name

  • C语言 深入理解动态规划之计数类DP

    目录 写在前面 石子合并 写在前面 之前讲过背包问题,线性DP,区间DP,不知道大家忘了吗,这次是计数类DP 石子合并 老规矩,先画图. 思路:把1,2,3, … n分别看做n个物体的体积,这n个物体均无使用次数限制,问恰好能装满总体积为n的背包的总方案数(完全背包问题变形) 初值问题: 求最大值时,当都不选时,价值显然是 0 而求方案数时,当都不选时,方案数是 1(即前 i 个物品都不选的情况也是一种方案),所以需要初始化为 1 即:for (int i = 0; i <= n; i ++)

  • C语言 深入理解动态规划之计数类DP

    目录 写在前面 石子合并 写在前面 之前讲过背包问题,线性DP,区间DP,不知道大家忘了吗,这次是计数类DP 石子合并 老规矩,先画图. 思路:把1,2,3, … n分别看做n个物体的体积,这n个物体均无使用次数限制,问恰好能装满总体积为n的背包的总方案数(完全背包问题变形) 初值问题: 求最大值时,当都不选时,价值显然是 0 而求方案数时,当都不选时,方案数是 1(即前 i 个物品都不选的情况也是一种方案),所以需要初始化为 1 即:for (int i = 0; i <= n; i ++)

  • Git的简单理解及基础操作命令详解

    git和svn有什么区别呢? git采用分布式版本库管理,而svn采用集中式版本库管理. 集中式版本库管理需要有一台存放版本库的服务器,开发人员在开发的时候分别从服务器拉取过来最新版本,然后创建/进入分支进行开发,开发完成之后将分支提交或者合并到主分支. 分布式版本库管理允许开发者们将版本库搬到自己的电脑上,在开发过程中,开发者们可以根据不同的目的创建分支和修改代码,开发完成后进行各项合并,这样做提高了开发的敏捷性和速度,并且减少了公共服务器的压力,且任意两个开发者之间的冲突更容易得到解决. g

  • angular2 ng2 @input和@output理解及示例

    angular2 @input和@output理解 先做个比方,然后奉上代码 比如: <talk-cmp [talk]="someExp" (rate)="eventHandler($event.rating)"> input, [talk]="someExp" 这个标签可以理解为一个专门的监听器,监听父组件传递过来的someExp参数,并存入自身组件的talk变:好像是开了个后门,允许且只允许父组件的someExp进入,一旦进入立刻

  • javascript深入理解js闭包

    一.变量的作用域 要理解闭包,首先必须理解Javascript特殊的变量作用域. 变量的作用域无非就是两种:全局变量和局部变量. Javascript语言的特殊之处,就在于函数内部可以直接读取全局变量. Js代码 var n=999; function f1(){ alert(n); } f1(); // 999 另一方面,在函数外部自然无法读取函数内的局部变量. Js代码 function f1(){ var n=999; } alert(n); // error 这里有一个地方需要注意,函数

  • 深入理解node exports和module.exports区别

    我们只需知道三点即可知道 exports 和 module.exports 的区别了: 1.exports 是指向的 module.exports 的引用 2.module.exports 初始值为一个空对象 {},所以 exports 初始值也是 {} 3.require() 返回的是 module.exports 而不是 exports 所以: • 我们通过 var name ='nswbmw'; exports.name = name; exports.sayName =function(

  • 深入理解AngularJs-scope的脏检查(一)

    进入正文前的说明:本文中的示例代码并非AngularJs源码,而是来自书籍<<Build Your Own AngularJs>>, 这本书的作者仅依赖jquery和lodash一步一步构建出AngularJs的各核心模块,对全面理解AngularJs有非常巨大的帮助.若有正在使用AngulaJs攻城拔寨并且希望完全掌握手中武器的小伙伴,相信能对你理解AngularJs带来莫大帮助,感谢作者. 在这篇文章中,希望能让您理清楚以下几项与scope相关的功能: 1.dirty-chec

随机推荐