Question

Knapsack Problem

将一群物品儘量塞进背包裡面，令背包裡面的物品总价值最高。背包没有容量限制，无论物品是什麽形状大小，都能塞进背包；但是背包有重量限制，如果物品太重，就会撑破背包。

以数学术语来说，背包问题就是选择一个最理想的物品子集合，在符合重量限制的前提下、求得最大的利益！

背包问题有很多变形，接下来将会一一介绍。

Fractional Knapsack Problem

Fractional Knapsack Problem

Fractional 是“分数”的意思。一个物品可以切下一部分、只取几分之几放进背包。

我们很容易就可以制定一个 Greedy 策略：价值与重量的比值最高的物品，优先放入背包。

总是用当下最好的物品填满背包空隙，最后没有留下任何空隙。每一份背包空间，都是最有价值的物品，就算是交换物品也无法增加总价值──显然是最佳解。

时间複杂度是 O(N)。其中 N 为物品数量。

0/1 Knapsack Problem

0/1 Knapsack Problem

“0/1”的意思是：每种物品只会放进背包零个或一个。一个物品要嘛整个不放进背包、要嘛整个放进背包。物品无法切割。

大家看到这个问题，第一个直觉通常是贪心法：优先挑选价值最高的物品。然而，价值高的物品，放入背包之后，有可能留下很大的空隙，浪费背包耐重量；反而是狂塞一些零零碎碎的不值钱东西，才能获得最多的利益。

聪明的人会想：优先挑选价值与重量比值最大的物品。不过这个方法也有问题，仍然有可能出现方才提到的现象。你能举例吗？这有助于了解 0/1 背包问题的关键点。

0/1 背包问题的关键点，在于如何有效利用背包的剩馀重量，找出最好的物品组合方式。

0/1 背包问题是经典的 NP-complete 问题，无法快速求得精确解，只能折衷求得近似解。然而，当数值范围不大时，得以用动态规划快速求得精确解。

本篇文章打算藉由 0/1 背包问题的各种细节，介绍动态规划的各种技巧。大纲如下：

让背包裡面的物品总价值最大
让背包裡面的物品总价值最小（背包不放东西就好了，没有什麽好讨论的。）
此时背包裡面放了哪些物品
此时背包裡面的物品有哪些不同的组合方式
此时背包裡面的物品有几种不同的组合方式
此时背包裡面的物品尽量最少（多）个
此时背包裡面的物品总重量，最少是多少、最多是多少

UVa 431 624 990 10130 10819 10980

让背包裡面的物品总价值最大（一）

穷举法是最基本的方法。针对全部物品，穷举所有子集合，找出物品总重量符合限制、物品总价值最大的子集合。

所有的子集合总共 O(2^N) 个，验证一个子集合需时 O(N)，所以时间複杂度为 O(2^N * N)。其中 N 是物品的数量。

物品的编号顺序是无所谓的。预先按照重量（或者是价值）排序所有物品，并且採用 backtracking 进行穷举，可以大幅减少计算时间。

让背包裡面的物品总价值最大（二）

动态规划是比较有效率的方法。分割问题的方式很简单：对某一件物品来说，我们可以选择放或不放；然后移去这件物品，缩小问题范畴。

一件物品不放进背包，背包价值不变、背包耐重不变；一件物品放进背包，背包价值上升、背包耐重下降。递迴公式为：

c(n, w) = max( c(n-1, w), c(n-1, w-weight[n]) + cost[n] )
               ^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
               不放 -> 0            有放 -> 1

n：第 0 个到第 n 个物品要放进背包内。
w：背包耐重限制。
c(n, w)：只有第 0 个到第 n 个物品，耐重限制为 w，此时的背包问题答案。
weight[n]：第 n 个物品的重量。
cost[n]：第 n 个物品的价值。

仔细考虑边界条件，例如耐重不足的情况、没有物品的情况：

c(n, w) =
 { -INF                                   , if w < 0
 { -INF                                   , if n < 0
 { 0                                      , if n = 0 and w >= 0
 { max( c(n-1, w),                        , if n > 0 and w >= 0
 {      c(n-1, w-weight[n]) + cost[n] )

避免存取负的物品、负的耐重：

c(n, w) =
 { 0                                      , if n = 0
 { c(n-1, w)                              , if n > 0
 {                                          and w-weight[n] < 0
 { max( c(n-1, w),                        , if n > 0
 {      c(n-1, w-weight[n]) + cost[n] )     and w-weight[n] >= 0

Unbounded Knapsack Problem

无限背包问题

物品有许多种类，每一种物品都无限量供应的背包问题。

UVa 10465

演算法

分割问题的方式可以仿照 0/1 背包问题。0/1 背包问题是一个物品的去留；无限背包问题则是一种物品的去留。考虑一种物品的各种用量：

c(n, w) = max(
   c(n-1, w - weight[n] * 0) + cost[n]     ,   用去零个第 n 种物品
   c(n-1, w - weight[n] * 1) + cost[n] * 1 ,   用去一个第 n 种物品
   c(n-1, w - weight[n] * 2) + cost[n] * 2 ,   用去两个第 n 种物品
   ... ,                                       ...
)

n：第 0 种到第 n 种物品要放进背包内。
w：背包耐重限制。
c(n, w)：只有第 0 种到第 n 种物品，耐重限制为 w，此时的背包问题答案。
weight[n]：第 n 种物品的重量。
cost[n]：第 n 种物品的价值。

时间複杂度是 O(NWW)，空间複杂度是 O(W)。

演算法

更好的方式，其实仍是一个物品的去留：

c(n, w) = max( c(n-1, w), c(n, w-weight[n]) + cost[n] )
                            ^^
                            只有这裡不同，因为物品无限量供应。

时间複杂度降低成 O(NW)，空间複杂度为 O(W)。

Bounded Knapsack Problem

有限背包问题

物品有许多种类，每一种物品都是限量供应的背包问题。

演算法

仿照无限背包问题，考虑每一种物品的用量：

c(n, w) = max(
   c(n-1, w - weight[n] * 0) + cost[n] * 0 ,   用去零个第 n 种物品
   c(n-1, w - weight[n] * 1) + cost[n] * 1 ,   用去一个第 n 种物品
   ... ,                                       ...
   c(n-1, w - weight[n] * number[n])           用去 number[n]个第 n 种物品
      + cost[n] * number[n]
)

n：第 0 种到第 n 种物品要放进背包内。
w：背包耐重限制。
c(n, w)：只有第 0 种到第 n 种物品，耐重限制为 w，此时的背包问题答案。
weight[n]：第 n 种物品的重量。
cost[n]：第 n 种物品的价值。
number[n]：第 n 种物品的数量。

时间複杂度是 O(NWM)，空间複杂度是 O(W)。其中 M 是物品数量最大值（不是总和）。

UVa 10086

演算法

Scaling Method。同种类的 M 个物品，实施二进位分解，重捆成 1、2、4、8、……、2^k、M - 2^k 个物品，一共⌈logM⌉捆。这些捆的 0/1 组合，可以凑出各种数量的物品。

一捆视作一个物品，直接套用 0/1 背包问题，物品数量从 N 变成 O(N * logM)。

时间複杂度是 O(NlogM * W)，空间複杂度是 O(W)。

演算法

http://www.cnblogs.com/GXZC/archive/2013/01/08/2851153.html

http://morris821028.github.io/2016/12/18/jg-20008/

各个同馀系分开处理，实施凸包优化，斜率皆是一，可视作 deque 优化。时间複杂度 O(NW)。

Money Changing Problem

各种相关问题

能否凑得某个价位（Money Changing Problem）
凑得某个价位的凑法总共几种（Coin Change Problem）
凑得某个价位的最少（多）钱币用量（Change-Making Problem）
凑得某个价位的最少（多）钱币种类
所有无法凑得的价位当中，最大的价位（Frobenius Number）
所有无法凑得的价位总共几种
限制钱币用量，求得 Frobenius Number 加一（Postage Stamp Problem）

能否凑得某个价位（Money Changing Problem）

给定许多种不同面额的钱币，能否凑得某个价位？每种面额的钱币都无限供应，一定够用。

Money Changing Problem 其实就是 Unbounded Knapsack Problem 的变形：物品变成钱币，物品重量变成面额，物品价值变成“凑得到、凑不到”两种情况，累计价值的方式从加法运算变成 OR 运算。

唯一要小心的是：表格的初始值，把 0 元设定为可以凑到；但是正常情况下，是无法凑到 0 元的。

c(n, m) = c(n-1, m) or c(n, m-price[n])
          ^^^^^^^^^    ^^^^^^^^^^^^^^^^
         不用这种钱币    用去一个钱币

n：用第 0 种到第 n 种钱币来凑得价位。
m：欲凑得的价位值。
c(n, m)：用第 0 种到第 n 种钱币凑得价位 m 的凑法数目。
price[n]：第 n 种钱币的面额大小。

Change-Making Problem

找钱问题

你去商店买东西，你掏出了一张百元钞票，买了一包 23 元的零食。柜员须找钱给你，但是你希望柜员找给你的硬币数目越少越好，如此口袋会轻一点。那麽柜员会给你几个硬币呢？

演算法（Cashier's Algorithm）

演算法非常直觉。填答案的原则：先找给你面额较高的硬币。

时间複杂度是 O(N)，N 是铜板种类。

Partition Problem

各种相关问题

一个数字集合，挑几个数字，总和恰为零（Subset Sum Problem）
一个数字集合，挑几个数字，总和恰为整体总和的一半（Partition Problem）
N 个不同重量物品，M 个不同耐重箱子，用最少箱子装所有物品（Bin Packing Problem）

通通可以套用 0/1 Knapsack Problem 的思维模式。

Banzhaf Power Index

有一项决策要投票表决，一人一票，不得投废票，过半数赞成则通过，反之则否决。投票者由许多派系组成，各个派系都相当团结，同样派系的人，要嘛全部都是投赞成票，要嘛全部都是投反对票。然而有些派系人多，有些派系人少，人多的派系能左右大局，人少的派系却势单力薄。于是产生一个问题：有能力对最终决策造成影响的是哪些派系？影响能力又是多少？

一个派系有能力对决策造成影响，是指所有派系都设定立场之后，此派系一旦改变立场，会马上颠倒决策结果。换个角度来说，是指此派系之外的所有派系都投完票之后，此派系若全数投赞成票，则会使决策顺利通过，反之若全数投反对票，则会使决策无法通过。

Banzhaf Power Index 的计算方式是这样的：一个派系 X 的 Banzhaf Power Index = 派系 X 影响决策的情况数目 ÷ (派系 1 影响决策的情况数目 + ... + 派系 N 影响决策的情况数目)。所有派系的 Banzhaf Power Index 的总和会是 1。

藉由 Banzhaf Power Index，可以看出各派系的实力，也可以看出投票表决是否公平。

1.
A 派系 9 票、B 派系 9 票、C 派系 7 票、D 派系 3 票、E 派系 1 票、F 派系 1 票。
总共投票数为 30 票。过半数之票数为 16 票。

2.
以 A 派系为例，A 派系影响决策的情况，一共有 16 种：

   AB AC ABC ABD ABE ABF ACD ACE ACF
   ABDE ABDF ABEF ACDE ACDF ACEF ADEF

派系有出现，表示投赞成票；派系无出现，表示投反对票。
拿掉 A 则会逆转决策结果。

3.
可以发现 D 派系、E 派系、F 派系，
完全无法介入结果，没有任何影响力：

  | votes | power |  BPI
--+-------+-------+-------
A |   9   |  16   | 16/48
B |   9   |  16   | 16/48
C |   7   |  16   | 16/48
D |   3   |   0   |   0
E |   1   |   0   |   0
F |   1   |   0   |   0
--+-------+-------+--------
  |  30   |  48   |  1.0

计算一个派系影响决策的情况数目

甲、移除此派系。
乙、剩馀派系进行投票，并算出各种不同总票数之下的情况数目。
丙、搜寻靠近过半票数的情况，累计这些情况数目。

是 Partition Problem 的延伸应用。

时间複杂度是 O(N^2 * S)，N 是派系数目，S 是总投票数，或者说是过半票数。