Knapsack Problem (背包问题)

Presentation on theme: "Knapsack Problem (背包问题)"— Presentation transcript:

1 Knapsack Problem (背包问题)
戴红伟

2 The Knapsack Problem Def: 有N个物品和一个背包，其中: 如何放置物品可得最高价值? 此问题可以表示为如下:
物品具有重量 (w1, w2, …, wn) 和价值 (p1, p2, …, pn) 背包的最大重量承受限制为W 如何放置物品可得最高价值? 此问题可以表示为如下:

3 Knapsack Problem问题类型 Fractional Knapsack Problem:
物品可以被任意分割 一般采用贪婪算法(Greedy Approach) 0/1 Knapsack Problem: 物品不可分割 一般采用动态规划法(Dynamic Programming) 参考：《算法设计与分析》王红梅 P150

4 其他类型背包问题 完全背包问题(0/1)： 多重背包问题
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 多重背包问题 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

5 分组背包问题： 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 有依赖的背包问题： 这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

6 适配背包问题： 有容量为S的背包，N件物品，重量分别为w1, w2, …, wn，从N件物品中挑选若干件物品，所选物品之和恰能放入该背包，即所选物品之和等于S。

7 授课内容 贪心法求解 最佳装载 背包问题 动态规划法求解 0/1 背包问题 遗传算法求解 0/1 背包问题

8 贪心法求解 最佳装载 背包问题 描述：对于容量为c的背包进行装载，从n个物品中选择装入背包的物品，每个物品i的重量和价值分别为wi和pi。在背包中物品的总重量不超过背包容量的前提下，求装入物品价值最高的装载法。 输入： 5 20 //物品的数量和背包的容量 6 3 //第一个物品的重量和价值 2 5 //… 3 8 10 6 7 4

9 输出： 1

10 解题思路 总是对当前问题作最好的选择，也就是局部寻优。现按物品效益、重量比值升序排列。然后每次选择比值大的物品进行装载，直到背包装满为止。

11 核心代码 //创建物品信息结构体

12

13

14 转换为价值重量比

15 2-动态规划法求解0/1背包问题 动态规划法设计算法一般分成三个阶段： （1）分段：将原问题分解为若干个相互重叠的子问题； （2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式； （3）求解：利用递推式自底向上计算，实现动态规划过程。 动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。

16 于是，问题归结为寻找一个满足约束条件式2.1，并使目标函数式2.2达到最大的解向量X=(x1, x2, …, xn)。
在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数： （式2.1） （式2.2） 于是，问题归结为寻找一个满足约束条件式2.1，并使目标函数式2.2达到最大的解向量X=(x1, x2, …, xn)。

17 证明0/1背包问题满足最优性原理。 设(x1, x2, …, xn)是所给0/1背包问题的一个最优解，则( x2, …, xn)是下面一个子问题的最优解： 如若不然，设(y2, …, yn)是上述子问题的一个最优解，则 因此， 这说明(x1, y2, …, yn)是所给0/1背包问题比(x1, x2, …, xn)更优的解，从而导致矛盾。

18 0/1背包问题可以看作是决策一个序列(x1, x2, …, xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, …, xi-1)，在决策xi时，问题处于下列两种状态之一： （1）背包容量不足以装入物品i，则xi=0，背包不增加价值； （2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：

19 [动态规划函数]: 3 第 i 物的重量比背包目 前可承受之重量还重 1装入0个物品 2 背包容量为0 （式2.3） （式2.4.1）
（式2.4.2） 5 放入第 i 物后可得的价值 4 不放入第 i 物可得的价值

20 式2.3表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。
式2.4的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况： （1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi； （2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。

21 例如，有5个物品，其重量分别是{2, 2, 6, 5, 4}，价值分别为{6, 3, 5, 4, 6}，背包的容量为10。
根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。 1 2 3 4 5 6 7 8 9 10 w1=2 v1=6 1 w2=2 v2=3 2 w3=6 v3=5 3 w4=5 v4=4 4 w5=4 v5=6 5

22 第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；
第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值； 依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品 时取得的最大价值。 1 2 3 4 5 6 7 8 9 10 w1=2 v1=6 w2=2 v2=3 w3=6 v3=5 11 14 w4=5 v4=4 13 w5=4 v5=6 12 15

23 如何确定装入背包的具体物品？ 从V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数： （式6.13）

24 1 2 3 4 5 6 7 8 9 10 x1=1 w1=2 v1=6 1 6 6 6 6 6 6 6 6 6 x2=1 w2=2 v2=3 2 6 6 9 9 9 9 9 9 9 x3=0 w3=6 v3=5 3 6 6 9 9 9 9 11 11 14 x4=0 w4=5 v4=4 4 6 6 9 9 9 10 11 13 14 x5=1 w5=4 v5=6 5 6 6 9 9 12 12 15 15 15

25 核心算法实现： 设n个物品的重量存储在数组w[n]中，价值存储在数组v[n]中，背包容量为C，数组V[n+1][C+1]存放迭代结果，其中V[i][j]表示前i个物品装入容量为j的背包中获得的最大价值，数组x[n]存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：

26 遗传算法求解 0/1 背包问题(仅做了解)

27 遗传算法基本原理 遗传算法的基本运算 ⑴ 选择算子 ⑵ 交叉算子 ⑶ 变异算子 模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传
空间，把可能的解编码成一个向量——染色体，向量的每个 元素称为基因。 X= 通过不断计算各染色体的适应值，选择最好的染色体，获 得最优解。 遗传算法的基本运算 ⑴ 选择算子 ⑵ 交叉算子 ⑶ 变异算子

28 xi 为种群中第i个染色体， ●选择算子 ——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲
区），为以后染色体交换、变异，产生新的染色体作准备。 选择方法——适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率：Pc xi 为种群中第i个染色体，

29 具体步骤 举例： ⒈具有6个染色体的二进制编码、适应度值、Pc累计 值。 1）计算各染色体适应度值
2）累计所有染色体适应度值，记录中间累加值S - mid 和最 后累加值 sum = ∑f(xi) 3） 产生一个随机数 N，0〈 N 〈 sum 4） 选择对应中间累加值S - mid 的第一个染色体进入交换集 5） 重复（3）和（4），直到获得足够的染色体。 举例： ⒈具有6个染色体的二进制编码、适应度值、Pc累计 值。

30 染色体的 适应度和所占的比例 用转轮方法进行选择

31 10个染色体种群按比例的选择过程 染色体被选的概率 被选的染色体个数 1 2 3 4 5 6 7 8 9 10 17 12 11 27 48
染色体编号 1 2 3 4 5 6 7 8 9 10 适应度 17 12 11 被选概率 0.1 0.02 0.22 0.09 0.16 0.14 0.03 适应度累计 27 34 36 48 59 66 69 76 被选的染色体个数 随机数 23 49 76 13 1 27 57 所选染色体号码 3 7 10

32 ●交叉算子 复制不能创新,交叉解决染色体的创新
方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体). 新的子辈染色体: A’ B’ 双点(two-point crossover)交叉，多点(multi-point crossover)交叉…

33 模拟生物在自然界环境变化,引起基因的突变.产生新的染色体，表现出新的性状。
●变异算子 模拟生物在自然界环境变化,引起基因的突变.产生新的染色体，表现出新的性状。 在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低. 基本位变异：以变异概率Pm随机指定某一位或者几位基因做上的基因值做变异运算； 均匀变异，边界变异等…

34 遗传策法的运算过程 选择(复制)： 根据各个个体的适应度，按照一 定的规则或方法，从第t代群体P(t) 中选择出一些优良的个体遗传到下
交叉： 将群体P(t)内的各个个体随机搭配 成对，对每一对个体，以某个概率 (称为交叉概率）交换它们之间的 部分染色体； 变异： 对群体P(t)中的每一个个体，以某一概率(称为变异概率)改变某 一个或某一些基因座上的基因值为其他基因值。 实际问题参数集 编码 随机产生群体t 计算适值 运算：复制 交叉 变异 群体t+1群体t 群体t+1 满足要求？ N Y 解码 改善或解决实际问题

35 注意约束条件

36 实验讲解 冲撞机器人问题

37 实验讲解——碰撞机器人 模拟与仿真的应用；
描述：在A*B大小的仓库种有N个机器人，每个机器人都有一个初始位置和方向，机器人按照指令进行移动，而且没有两个机器人同时移动。每个机器人占据直径为1的圆形区域。 如果企图移动出仓库的范围，则判断为撞墙；如果两个机器人占据同样的位置，则判断为冲撞。

38 输入 第一行K，测试序列的组数； 每个测试序列开始一行是两个整数A B，1<=A,B<=100，给定仓库大小。A是东西方向，B是南北方向。第二行是两个整数M N，1<=N, M<=100，分别表示机器人的数目和指令的数目。随后两行包括2个整数1<=Xi<=A,1<=Yi<=B和一个字母（N S E W）表示位置和方向，没有两个机器人的初始位置是相同的。

39

40 最后M行顺序给定所有指令。 指令格式如下： <机器人编号> <操作> <次数> 其中有3种操作： L——左转90度 R——右转90度 F——向前一个单位 1<= 次数 <= 100

41 输出 对于每个测试序列，输出一行： 机器人撞墙（Robot i crashes into the wall）
Robot i crashes into robot j. (i是移动机器人) OK（没有发生冲撞）

42 解题思路 二维数组保存所有机器人的位置，数组元素的值就是占据该网格的机器人的编号，如果网格没有被占有，值为0；
用一个数组记录机器人的方向，值为0～3，表示（东北西南）4个方向。左转值增加，右转值减少，结果需要模4。方向改变不会导致机器人碰撞。 蛮力法模拟机器人的移动，每次移动一格，如果下个位置是墙或者有别的机器人，则发生碰撞。

43 输入样例 1 5 4 2 2 1 1 E 5 4 W 1 F 7 2 F 7

44 输出样例 Robot 1 crashes into the wall

45

46

47 实验安排 时间：20090429(周三) 16：40～18：15 地点：计算机楼二楼机房 内容：
时间： (周三) 16：40～18：15 地点：计算机楼二楼机房 内容： 动态规划法求解如下0/1背包问题：5个物品重量和价值分别为{3，2，1，4，5}{25，20，15，40，50}，背包容量为6。 贪心算法求解订票问题： 某公司以出售某一固定数量的连号票（套票）来代替单张售票，套票的订单以该套票中最小的座位号为标志。如果一个订单完全按照观众要求，那么观众付全价（2元），如果一个订单虽被接受，但是至少有一个座位与观众要求不同，那么顾客只要付半价（1元），问怎样销售才能使收入最高。

48 service.in Service.out 其他授课内容实验作业； 20 3 //总座位数，套票所含座位数； 7
//总座位数，套票所含座位数； 7 Service.out 9 //最大收入 6 //订单数 //第4位观众的座位从座位号1开始 1 4 2 7 3 10 6 13 5 16 其他授课内容实验作业；