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

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）问题描述