当前位置：文档之家 › 背包问题九讲 2.0

背包问题九讲 2.0

  • 格式：pdf
  • 大小：238.10 KB
  • 文档页数：16

背包问题九讲 2.0 beta1崔添翼 (Tianyi Cui)*2011-09-20†

本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。这系列文章的第一版于2007年下半年使用EmacsMuse制作，以HTML格式发布到网上，转载众多，有一定影响力。2011年9月，本系列文章由原作者用LATEX重新制作并全面修订，您现在看到的是2.0 alpha版本，修订历史及最新版本请访问https://github.com/tianyicui/pack查阅。本文版权归原作者所有，采用CCBY-NC-SA协议发布。

Contents101背包问题21.1题目....................................21.2基本思路..................................31.3优化空间复杂度.............................31.4初始化的细节问题............................41.5一个常数优化...............................41.6小结....................................4

2完全背包问题52.1题目....................................52.2基本思路.................................52.3一个简单有效的优化..........................52.4转化为01背包问题求解.........................52.5O(VN)的算法..............................62.6小结....................................6

3多重背包问题63.1题目....................................63.2基本算法..................................73.3转化为01背包问题............................73.4可行性问题O(VN)的算法........................83.5小结....................................8

*a.k.a.dd_engi

†Build 20110920100800

14混合三种背包问题84.1问题....................................84.201背包与完全背包的混合........................84.3再加上多重背包.............................94.4小结....................................9

5二维费用的背包问题95.1问题....................................95.2算法....................................105.3物品总个数的限制............................105.4复整数域上的背包问题.........................105.5小结....................................10

6分组的背包问题106.1问题....................................106.2算法....................................106.3小结....................................11

7有依赖的背包问题117.1简化的问题................................117.2算法....................................117.3较一般的问题...............................127.4小结....................................12

8泛化物品128.1定义....................................128.2泛化物品的和...............................138.3背包问题的泛化物品..........................138.4小结....................................13

9背包问题问法的变化139.1输出方案..................................149.2输出字典序最小的最优方案......................149.3求方案总数................................159.4最优方案的总数.............................159.5求次优解、第K优解..........................159.6小结....................................16

101背包问题1.1题目有N件物品和一个容量为V的背包。放入第i件物品耗费的费用是Ci1，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

1也即占用背包的空间容量，后文统一称之为“费用(cost)”

21.2基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即F[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

F[i,v]=max{F[i−1,v],F[i−1,v−Ci]+Wi

}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i−1件物品相关的问题。如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为v的背包中”，价值为F[i−1,v]；如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为v−Ci的背包中”，此时能获得的最大价值就是F[i−1,v−Ci]再加上通过放入第i

件物品获得的价

值Wi。伪代码如下：

F[0,0..V]←0fori←1toNforv←CitoVF[i,v]←max{F[i−1,v],F[i−1,v−Ci]+Wi

}

1.3优化空间复杂度以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O(V)。先考虑上面讲的基本思路如何实现，肯定是有一个主循环i←1...N，每次算出来二维数组F[i,0...V]的所有值。那么，如果只用一个数组F[0...V]，能不能保证第i次循环结束后F[v]中表示的就是我们定义的状态F[i,v]呢？F[i,v]是由F[i−1,v]和F[i−1,v−Ci]两个子问题递推而来，能否保证在推F[i,v]

时（也

即在第i次主循环中推F[v]时）能够取用F[i−1,v]和F[i−1,v−Ci]

的值呢？

事实上，这要求在每次主循环中我们以v←V...0的递减顺序计算F[v]，这样才能保证计算F[v]时F[v−Ci]保存的是状态F[i−1,v−Ci]的值。伪代码如下：

F[0..V]←0fori←1toNforv←VtoCi

F[v]←max{F[v],F[v−Ci]+Wi

}

其中的F[v]←max{F[v],F[v−Ci]+Wi

}一句，恰就对应于我们原来的转移方

程，因为现在的F[v−Ci]就相当于原来的F[i−1,v−Ci]。如果将v

的循环顺序

从上面的逆序改成顺序的话，那么则成了F[i,v]由F[i,v−Ci]

推导得到，与本题

意不符。事实上，使用一维数组解01背包的程序在后面会被多次用到，所以这里抽象出一个处理一件01背包中的物品过程，以后的代码中直接调用不加说明。

defZeroOnePack(F,C,W)forv←VtoCF[v]←max(F[v],f[v−C]+W)

3有了这个过程以后，01背包问题的伪代码就可以这样写：F[0..V]←0fori←1toNZeroOnePack(F,Ci,Wi)

1.4初始化的细节问题我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法，要求恰好装满背包，那么在初始化时除了F[0]为0，其它F[1..V]均设为−∞，这样就可以保证最终得到的F[V]是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将F[0..V]全部设为0。这是为什么呢？可以这样理解：初始化的F数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。这个小技巧完全可以推广到其它类型的背包问题，后面不再对进行状态转移之前的初始化进行讲解。

1.5一个常数优化上面伪代码中的fori←1toNforv←VtoCi

中第二重循环的下限可以改进。它可以被优化为

fori←1toNforv←Vtomax(V−ΣNiWi,Ci)

这个优化之所以成立的原因请读者自己思考。（提示：使用二维的转移方程思考较易。）

1.6小结01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想。另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及空间复杂度怎样被优化。

4

合集下载

运筹学及其应用9.3 背包问题

运筹学及其应用9.3 背包问题

此模型解决的是运输工具包括卫星的最优装载问题。 其数学模型为：
1
设 xi为第 i 种物品装入的件数，则背包问题可归结为如下
形式的整数规划模型：
n
∑ max z = gi (xi ) i =1
∑ n
i=1
ai xi
≤
a
xi ≥ 0
整数 （i = 1,2,L, n)
下面从一个例子来分析动态规划建模。
9.3 背 包 问 题
一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a (千克)，现有n种物品可供他选择装入 背包。第i种物品的单位重量为 ai (千克)，其价值（可以是表
明本物品对登山者的重要性指标）是携带数量 xi 的函数
gi ( xi )（i=1，2，…n）.问旅行者应如何选择携带物品的件 数，以使总价值最大？
x1
+ 4x2 + 5x3 ≤ xi ≥ 0, 整数
10
(i = 1,2,3)
5x3
s3 = s4 − 5x3 货物3
s4 = 10
g1 ( x1 ) = 4 x1
g2(x2 ) = 5x2
g3(x3) = 6x3
K=2 时 其中
f2 (s3)
=
max {g
0≤4 x2 ≤s3
2
(
x2
)
+
f1(s2 )}
3
x1
+ 4x2 + 5x3 ≤ xi ≥ 0, 整数
10
(i = 1,2,3)
5x3 s3 = s4 − 5x3
货物3
s4 = 10
g1 ( x1 ) = 4 x1
g2(x2 ) = 5x2
实验二,背包问题课件

实验二,背包问题课件

1
在背包容量为J时
Y
第i个物品能否放入
N
根据放入后是否有 利决定是否放入
不放入，背包 价值不变
J++ N
J= =C
Y I--
2019/10/9
I= =1
N
4
Y
第一个物
品
Y
能否放入
N
根据放入后是否有 利决定是否放入
不放入，背包 价值不变
输出（j,m(I,j)）矩阵
Y X[I]=0,不装入
for(int d=0;d<c;d++)
m[0][d]=0;
cout<<"输出(j,m(i,j))的矩阵："<<endl;
for(int a=0;a<=n;a++)
{ for(int b=0;b<=c;b++)
cout<<m[a][b]<<" ";
cout<<endl; }
cout<<endl;
}2019/10/9
实验二
0/1背包问题
2019/10/9
1
程序流程图：
J--背包的现有容量 C--背包的最大容量 V(i)—物品的价值（I=1,2,3,4,5） M—背包的价值
2019/10/9
2
在背包容量为J时
Y
第n个物品能否放入
N
背包价值为V(n)
背包价值为0
J++ N
J= =C
Y
2019/10/9
9
void traceback()
{
cout<<“输出表示装入情况的数组(1表示装入，0表示不
背包九讲之八：背包问题求方案数

背包九讲之八：背包问题求方案数

背包九讲之⼋：背包问题求⽅案数有 N 件物品和⼀个容量是 V 的背包。

每件物品只能使⽤⼀次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包容量，且总价值最⼤。

输出最优选法的⽅案数。

注意答案可能很⼤，请输出答案模 10⁹+7 的结果。

输⼊格式第⼀⾏两个整数，N，V，⽤空格隔开，分别表⽰物品数量和背包容积。

接下来有 N ⾏，每⾏两个整数 vi,wi，⽤空格隔开，分别表⽰第 i 件物品的体积和价值。

输出格式输出⼀个整数，表⽰⽅案数模 10⁹+7 的结果。

数据范围0<N,V≤10000<vi,wi≤1000输⼊样例4 51 22 43 44 6输出样例2法⼀：根据体积恰好为j时价值的⼤⼩来更新⽅案数1 #include<iostream>2 #include<climits>3 #include<algorithm>4using namespace std;5const int n = 1001;6int N, V, v, w, f[n], g[n];//f[j]、g[j]分别表⽰体积恰好为j时的最⼤价值、⽅案数7int mod = 1000000007;8int main() {9 cin >> N >> V;10 g[0] = 1;11for (int i = 1; i <= V; ++i)12 f[i] = INT_MIN; //除0以外，全部设为负⽆穷，确保都是从f[0]传递过去的13for (int i = 0; i < N; ++i) {14 cin >> v >> w;15for (int j = V; j >= v; --j) {16int s = 0, t = max(f[j], f[j - v] + w);17if (t == f[j])18 s += g[j]; //添加不更新的⽅案19if (t == f[j - v] + w)20 s += g[j - v]; //添加更新的⽅案21if (s >= mod)22 s -= mod;23 f[j] = t;24 g[j] = s;25 }26 }27int maxn = 0, res = 0;28for (int i = 0; i <= V; ++i)29 maxn = max(maxn, f[i]); //获取最⼤价值30for (int i = 0; i <= V; ++i)31if (maxn == f[i]) { //等于最⼤价值的⽅案都添加32 res += g[i];33if (res >= mod)34 res -= mod;35 }36 cout << res;37 }法⼆：根据体积最⼤为j时价值的⼤⼩来更新⽅案数1 #include<iostream>2 #include<climits>3 #include<algorithm>4using namespace std;5const int n = 1001;6int N, V, v, w, f[n], g[n];//f[j]、g[j]分别表⽰体积最⼤为j时的最⼤价值、⽅案数7int mod = 1000000007;8int main() {9for (int i = 0; i < n; ++i)10 g[i] = 1; //默认体积最⼤为i时⽅案数为111 cin >> N >> V;12for (int i = 0; i < N; ++i) {13 cin >> v >> w;14for (int j = V; j >= v; --j) {15if (f[j] < f[j - v] + w) {16 f[j] = f[j - v] + w;17 g[j] = g[j - v]; //使⽤新⽅案时更新⽅案数为g[j-v]的⽅案数18 }19else if (f[j] == f[j - v] + w)20 g[j] = (g[j] + g[j - v]) % mod; //原⽅案数加跟新⽅案数21//使⽤原⽅案时⽅案数不变，故不作操作。

背包问题

背包问题


完全背包问题也是一个相当基础的背包问题，它有两个状态转移方程，分别在“基本思路”以及“O(VN） 的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会，不仅记住，也要弄明白它们是怎么得 出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如 何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关 的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令 f[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程， 像这样：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。这跟01背包问题一样有O(N*V）个状态需要求解，但求解每个状态的 时间则不是常数了，求解状态f[v]的时间是O(v/c），总的复杂度是超过O(VN）的。
背包问题已经研究了一个多世纪，早期的作品可追溯到1897年 数学家托比亚斯·丹齐格（Tobias Dantzig， 1884-1956）的早期作品 ，并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
应用
1998年的石溪布鲁克大学算法库的研究表明，在75个算法问题中，背包问题是第18个最受欢迎，第4个最需 要解决的问题（前三为后kd树，后缀树和bin包装问题）。
基础背包
题目 基本思路
空间复杂 示例程序
递归实现 程序
测试数据 总结
有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些 物品的重量总和不超过背包容量，且价值总和最大。