算法作业十- 0-1 背包问题

本文主要是介绍算法作业十- 0-1 背包问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、问题
有n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中第i个集装箱的重量为wi，要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。
注意，在满足的条件下才可能将这个集装箱装上这2艘轮船。
2、解析
解该类问题的思路是轻者先装，直到再装任何集装箱将使轮船载重量超过 C 时停止.在这之前我们首先明白一个定理：对于任何正整数 k，算法（轻者先装）对 k 个集装箱的实例得到最优解
以下为该定理的证明：
在这里是通过数学归纳法来证明的。
（1）k=1,只有 1 个集装箱，其重量小于 C。任何装法都只有一种方式，
因此都是最优解，因此轻者先装也是最优解。
（2）归纳假设：假设算法对于规模为 k 的输入都能得到最优解。
考虑规模为 k+1 的输入，N={1，2，3，…k+1}，w={w1，w2，…, wk+1}是集装箱重量， w1<=w2<=…<= wk+1。
从 N 中拿掉最轻的集装箱，得到 k 规模的输入：
N’=N-{1}={2，3，…,k+1}
W’=W-{w1}
C’=C-w1
根据归纳假设，对于 k 个输入，N’、W’、C’的最优解为 I’，即
I’为 N’，不含 1 的最优解（归纳假设得），
令I=I’U{1},那么 I 必然是 N 的最优解，这也是算法对于 N,W,C 的解.
证明：I 必然是 N 的最优解，采用反证法，即假设 I 不是 N 的最优解。

（1）构建最优解 I*（N，含 1）：假设 I 不是 N 的最优解。则必然存在
最优解 I*，如果 I中没有 1，用 1 替代 I中的第一个集装箱标号得到的解也是
最优解（个数不变，因此也是最优解），使得 I为包含 1 的关于 N 的最优解， 且|I|>|I|。 （2） 构建最优解 I*’（ N’，不含 1）：因为 I为包含 1 的关于 N
的最优解，构建的 I’=I*-{1}是不包含 1 的最优解（待证明），即关于 N’、 W’、C’的最优解（N’、W’、C’不包含 1）。
（3）构建的最优解 I*’与归纳假设的最优解 I’比较：由（1）
|I*|>|I|得，| I*’|= |I*-{1}|>|I-{1}|=|T’|，与 I’的最优性矛盾（最优解 I*-
{1}大于最优解 I’）
3、设计
（1）将W1，W2，…，Wn按照递降排序（降序的目的是加快回溯，大的数据容易超出船1的载重）。
（2）解向量<X1，X2，…，Xn>，其中Xi∈{0，1}，1 <= i <= n搜索空间是子集树。
（3）在结点<X1，X2，…，Xk>的约束条件：∑WiXi <= C1
（4）满足多米诺条件：P（X1，X2，…，Xk+1）是（X1，X2，…，Xk+1）的某个性质
P（X1，X2，…，Xk+1）-> P（X1，X2，…，Xk）（0 < k < n）
要使回溯算法得到正确应用，必须满足多米诺性质
N皇后放置在彼此不能攻击的位置
背包问题
设Xi = ∑Xk * Wk，Xi+1 = ∑Xk * Wk
∵Xi+1 <= C，Wk > 0，Xk ∈{0，1}
∴Xi < Xi+1 <= C
装载问题
此处，P（X1，X2，…，Xk）= ∑WiXi > C1
∑WiXi > C1 ->∑WiXi > C1
∑WiXi<=C1->∑WiXi <= C1

4、分析
O（2^n）
5、源码
https://github.com/QiuYuSY/AlgorithmWork/blob/master/src/xsr/tenthLesson/tenthLesson.java

这篇关于算法作业十- 0-1 背包问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！