临时小驻

求仁得仁,复无怨怼。

背包问题

2018-01-09 02:44:00 +0800

本文提炼自背包九讲,我们将讨论 01-背包、部分背包、完全背包、多重背包、多维代价的背包、分组背包。

01-背包问题

01-背包是这样的问题:有 N 件物品,分别重 w[i],值 v[i]。有一个背包,容量 W,每件物品只能完全装或者不装,求装哪些能使背包中物品的总价值最大,最大是多少。

当背包容量 W 时,前 i 个物品考虑完的价值,有两个策略:

  1. 不装第 i 个物品,价值与背包容量 W 且考虑完前 i-1 个物品的价值相同;
  2. 装第 i 个物品,价值与背包容量 W-w[i] 且考虑完前 i-1 个物品的价值相同。

这是一个递归过程。能够发现,当我们在第 i 轮取到了最优解(较大值),那么参与考虑的第 i-1 轮的那两个选择也必定是最优解。

使 F[i,W] 表示容量为 W 时,前 i 个物品考虑完后的最大价值。那么我们可以得到如下的状态转移方程

F[i,W] = max{ F[i-1,W], F[i-1,W-w[i]] + v[i] }

最大总价值为 F[N,W]。

下面就使用这个方程,写出算法

初始化:

int F[0..N][0..W];
F[0, 0..W] = 0;

如果额外要求恰好装满背包,那么:

F[0,0] = 0;
F[0,1..W] = -inf;

基本算法:

int F[0..N][0..W];
int w[1..N], v[1..N];

for (int i = 1; i <= N; ++i)
    for (int j = w[i] j <= W; ++j)
        F[i, j] = max(F[i-1, j], F[i-1, j-w[i]] + v[i]);

因为目标是求 F[N,0..W] 中的值,因此可以只保留 F[n-1, 0..W] 的值:

int F[0..W];
int w[1..N], v[1..N];

for (int i = 1; i <= N; ++i)
    for (int j = W; j >= w[i]; --j) // 这是为了使 F[j-w[i]] 能获取到上一轮的值
        F[j] = max(F[j], F[j-w[i]] + v[i])

在只需知道 F[W] 时,还可做常数优化:

for (int i = 1; i <= N; ++i) {
    int lowbound = max(w[i], W-sum(w[i..N]));
    for (int j = W; j >= lowbound; --j) {
        F[j] = max(F[j], F[j-w[i]] + v[i])
    }
}

总结思路,我们用到了两个性质:

  1. 最优子结构:原问题的最优解,依赖于子问题的最优解。因此可递归拆分。
  2. 重叠子问题:在求解原问题时多次运用了同一个子问题的解。因此可临时存储子问题的解,避免重复计算。

满足这两个性质,就可以使用动态规划思想求解。

部分背包问题(物品可拆分的背包问题)

与 01-背包不同的地方在于,每件物品都可以把重量和价值等比例拆分,使背包只容纳物品的一部分。

有 N 件物品,分别重 w[i],值 v[i]。有一个背包,容量 W,每件物品都可以等比例拆分,把一部分装进背包,求怎么装能使背包中物品的总价值最大,最大是多少。

能够想到,既然可等比例拆分,那么按单位重量下的价值(称为单位价值)排序,从大到小依次取直到背包满为止,即可得到最大总价值。

这种按照一个策略,不因变化而改变策略(不在多个分支中挑选,只走一条路),称为贪心思想

这样做为什么是对的?

假如这个策略得到的不是最优解,那么最优解的选择里一定存在某个取了单位价值较低的物品,显然,在同样重量下总价值不可能比我们贪心策略得到的高,不存在这样的最优解。

什么情况下可以使用贪心思想求解?当问题满足拟阵性质。

拟阵(matroid)是抽象自线性代数和图论等领域的一个概念,因为在多个领域都有独立发现和归纳,因此可以用多个领域的术语来定义它。拿图论的独立集来定义,最终就是这么一个概念:

拟阵是一个二元组 $M=(S,L)$,满足

  1. S 是有限非空集合,L 是 S 子集的非空族(族可视为集合的集合);
  2. L 满足遗传性质:$A \subseteq B, B \in L \Rightarrow A \in L$;
  3. L 满足交换性质:$A,B \in L, A \lt B \Rightarrow \exists x \in B-A, A \cup { x } \in L$。

当发现目标解满足拟阵性质,那么采用贪心算法即可得到最优解。

完全背包问题

与 01-背包不同的地方在于,每种物品都有无限多个副本。

有 N 种物品,分别重 w[i],值 v[i],每种物品有无限多个。有一个背包,容量 W,每件物品只能完全装或者不装,求装哪些能使背包中物品的总价值最大,最大是多少。

这也是一个动态规划问题。

状态转移方程

F[i,W] = max{ F[i−1,W−k∗w[i]] + k∗v[i] | 0 ≤ k∗w[i] ≤ W }

这里的 k 是指第 i 种物品取 k 个。

优化思路:

  • 筛选不可用物品:若 w[i] > W,则直接舍弃物品 i。
  • 筛选低性价比物品:若 w[i] >= w[j] && v[i] < v[j],则直接舍弃物品 i。

根据上述状态转移方程,实质上做了转化:考虑到第 i 种物品最多 c[i] = floor(W/w[i]) 件,那就认为有 c[i] 件,然后求解这个 01-背包问题。

二进制思想优化的 01-背包:

根据二进制位运算的思想,总可以把某一数值看做若干个不同权值的位的加和,如 6=(110)。

把第 i 种物品拆成费用为 w[i]2^k、价值为 v[i]2^k 的若干件物品,其中 k 取遍满足 w[i]*2^k ≤ W 的非负整数。这样使得尝试次数下降了 log 级。

多重背包问题

在 01-背包和完全背包之间,

有 N 种物品,分别重 w[i],值 v[i],每种物品有 c[i] 个。有一个背包,容量 W,每件物品只能完全装或者不装,求装哪些能使背包中物品的总价值最大,最大是多少。

状态转移方程

F[i,W] = max{ F[i−1,W−k∗w[i]] + k∗v[i] | 0 ≤ k ≤ c[i] }

可化为二进制思想优化的01背包。

令这些系数分别为 1,2,4..2^(k−1), r = c[i]−2^k+1,其中 k 是满足 r > 0 的最大整数。

void ZeroOnePack(int w, int v, int n) {
    for (int i = n; i >= w; --i)
        F[i] = max(F[i], F[i-w] + v);
}

void CompletePack(int w, int v, int n) {
    for (int i = w; i <= n; ++i)
        F[i] = max(F[i], F[i-w] + v);
}

int MultiPack() {
    memset(F, 0, sizeof(F));
    for (int i = 1; i <= N; ++i) {
        if (c[i] * w[i] > W) {
            CompletePack(w[i], v[i], W);
        } else {
            int k = 1;
            while (k < c[i]) {
                ZeroOnePack(k*w[i], k*v[i], W);
                c[i] -= k;
                k <<= 1;
            }
            ZeroOnePack(c[i]*w[i], c[i]*v[i], W);
        }
    }
    return F[N];
}

当只要求判断能否填满给定容量背包时,可以采用如下思想:
F[i,j]表示用前i种物品填满容量j的背包时,还剩下多少个第i种物品。

多维度约束的背包

此时扩充原代价 w[i] 为 w[i][j],思路不变。

分组的背包问题

每组的物品最多只能选一个。

状态转移方程为

F[k,W] = max{F[k−1,W], F[k−1, W-w[i]] + v[i] | item i ∈ group k}

有依赖关系的背包问题

//TODO

原文链接 https://blog.xupu.name//p/2018-01-knapsack-problem/

如无特别指明,本站原创文章均采用 CC BY-NC-ND 4.0 许可,转载或引用请注明出处,更多许可信息请查阅这里