用 Groovy 解决背包问题

作者: Paul King
发布时间: 2024-02-09 03:00PM

背包问题是一个组合优化问题。给定一组物品，每个物品都有一个特定的重量和价值，确定将哪些物品放入背包（或其他容器）中，以最大限度地提高背包内的价值，而不超过给定的重量限制。

A knapsack and some gems

案例研究

对于我们的案例研究，我们将从将宝石放入背包开始。宝石具有以下特征

索引  重量  价值

0

1

1

1

2

5

2

3

10

3

5

15

4

6

17

宝石要么在背包中，要么不在背包中。这被称为问题的 0/1 背包变体。我们稍后会看看其他变体。

那么，我们的目标是找出将哪些宝石放入背包以最大限度地提高价值。

A knapsack and some gems

暴力破解

我们可能采用的第一个方法是简单地尝试所有可能的组合，丢弃任何超过重量限制的组合，然后找到剩下的组合的最大值。

一种方法是生成所有可能的索引组合。然后，选择满足背包重量约束的组合。然后，找到产生最高价值的组合，如下所示

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
int W = 10

var totalValue = { it*.v.sum() }
var withinLimit = { it*.w.sum() <= W }
var asTriple = { [i:it, w:weights[it], v:values[it]] }

var best = weights
    .indices
    .collect(asTriple)
    .subsequences()
    .findAll(withinLimit)
    .max(totalValue)

println "Total value for capacity $W = ${totalValue(best)}"
println "Gems taken: ${best*.i}"
println "Gem weights: ${best*.w}"

更详细地说，我们首先定义三个辅助闭包，totalValue、withinLimit 和 asTriple。将我们的数据收集到映射列表（三元组）中不是必需的，但它简化了后续处理。一旦我们有了数据，我们找到子序列，保留在重量限制内的子序列，然后找到最大值。

运行此脚本将产生以下输出

Total value for capacity 10 = 30
Gems taken: [1, 2, 3]
Gem weights: [2, 3, 5]

虽然这很简单，但它没有提供许多优化机会。对于像案例研究这样的小问题，优化并不重要，但对于更大的问题，组合的数量可能会呈指数级增长，我们需要注意这一点。

相反，让我们考虑一个递归解决方案，它让我们可以为将超过背包最大重量限制的情况提前退出

int solve(int[] w, int[] v, int W) {
    knapsack(w, v, v.length, W)
}

int knapsack(int[] w, int[] v, int n, int W) {
    if (n <= 0) {
        0
    } else if (w[n - 1] > W) {
        knapsack(w, v, n - 1, W)
    } else {
        [knapsack(w, v, n - 1, W),
         v[n - 1] + knapsack(w, v, n - 1, W - w[n - 1])].max()
    }
}

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
[6, 8, 10].each {
    println "Total value for capacity $it = ${solve(weights, values, it)}"
}

在这里，我们考虑每个宝石（对于给定的阶段，宝石 n 或索引 n - 1）。有两种路径可以计算，一种是宝石包含，另一种是宝石排除。我们记住从两条路径返回的最大值并继续处理。当宝石被包含时，我们然后解决将剩余宝石放入概念上更小的背包的较小问题。如果将宝石放入背包会导致重量超过限制，那么我们可以丢弃该路径以进行进一步处理。

将上述过程可视化为一个解决方案树是有用的（显示为容量 10）

brute force tree

浅红色节点表示可以跳过后续处理解决方案树的位置。

我们在这里计算了三种不同背包重量限制（6、8 和 10）的结果。输出如下所示

Total value for capacity 6 = 17
Total value for capacity 8 = 25
Total value for capacity 10 = 30

与 32 种组合（我们 5 个宝石的 2^5）相比，我们只处理了 11、16 和 21 种组合，其中两条路径都在最大重量限制分别为 6、8 和 10 时遍历。

更重要的是，我们将有更多的优化机会。一个快速解决方案是记忆化（缓存）调用 knapsack 方法的结果。Groovy 使这变得容易。与上面的唯一区别是添加了 @Memoized 注释

@Memoized
int knapsack(int[] w, int[] v, int n, int W) {
    if (n <= 0) {
        0
    } else if (w[n - 1] > W) {
        knapsack(w, v, n - 1, W)
    } else {
        [knapsack(w, v, n - 1, W),
         v[n - 1] + knapsack(w, v, n - 1, W - w[n - 1])].max()
    }
}

运行它将产生与之前相同的结果，但 knapsack 方法的执行次数从 44 次减少到 32 次（仅计算重量限制为 10 的背包时），以及从 107 次减少到 49 次（计算 6、8 和 10 时）。

使用分支限界法

另一种常用于优化的技术是分支限界法。它是分治一般原则的一种特殊形式；通过将一个大问题分解成较小的问题来解决它。

分治法类似于我们对上面的递归解决方案所做的事情，但对于分支限界法，我们执行更智能的消除。在处理一个分支的子节点之前，会根据某个最优解的上下估计界限来检查该分支。如果我们能够确定向下走该路径不可能比向下走某些替代路径更好，那么就会终止对给定路径的处理。对于背包问题，我们可以通过找到允许使用背包物品的有限数量的最优“贪婪”解来计算出这些界限。我们将在本博文的最后示例中介绍有限数量。事实证明，我们可以非常有效地计算它们。

首先，我们将创建一个 Item 记录来保存我们的重量和价值。

record Item(int weight, int value) {}

接下来，我们将创建一个 Node 来保存有关特定点候选解的当前状态的信息，该信息位于我们的解决方案树中

@Canonical
class Node {
    int level, value, weight
    public int bound

    static Node next(Node parent) {
        new Node(parent.level + 1, parent.value, parent.weight)
    }
}

接下来，bound 方法使用最优（贪婪）算法计算权重。这将需要我们允许宝石的有限部分才能准确，但在我们的情况下，我们只是将其用作界限。将其视为根据最坏情况和最佳情况进行估计。

int bound(Node u, int n, int W, List<Item> items) {
    if (u.weight >= W)
        return 0

    int valueBound = u.value
    int j = u.level + 1
    int totalWeight = u.weight

    while (j < n && totalWeight + items[j].weight <= W) {
        totalWeight += items[j].weight
        valueBound += items[j].value
        j++
    }

    if (j < n)
        valueBound += (int) ((W - totalWeight) * items[j].value / items[j].weight)

    valueBound
}

现在，我们的 knapsack 方法将按每单位重量的最高价值对宝石进行排序，然后遍历它们，记录每一步的界限。

int knapsack(int W, List<Item> items, int n) {
    items.sort { it.value / it.weight }
    var q = new PriorityQueue<>((a, b) -> b.bound <=> a.bound)
    Node u, v

    q.offer(new Node(-1, 0, 0))

    int bestValue = 0

    while (q) {
        u = q.poll()

        if (u.level == n - 1)
            continue
        else
            v = Node.next(u)

        v.weight += items[v.level].weight
        v.value += items[v.level].value

        if (v.weight <= W && v.value > bestValue)
            bestValue = v.value

        v.bound = bound(v, n, W, items)

        if (v.bound > bestValue)
            q.offer(v)

        v = Node.next(u)
        v.bound = bound(v, n, W, items)

        if (v.bound > bestValue)
            q.offer(v)
    }

    bestValue
}

int W = 10

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
var items = values.indices.collect {
    new Item(weights[it], values[it])
}

println "Total value for capacity $W = ${knapsack(W, items, values.length)}"

这有以下可视化（容量为 10）

branch and bound tree

我们应该注意，除了丢弃超过重量限制的不可行路径（浅红色）外，我们现在还丢弃了无用的路径（浅紫色），因为我们的界限值告诉我们，这些路径永远不会超过我们已经知道的某些替代最佳路径。

它有以下输出

Total value for capacity 10 = 30

使用动态规划

可以将动态规划视为分支限界技术的一种特殊情况。它也可以被认为类似于我们之前看到的记忆化。在这种情况下，Groovy 没有为我们提供缓存，我们自己在 dp 数组中跟踪它

int solve(int[] v, int[] w, int W) {
    knapsack(new Integer[v.length][W+1], v, w, W, 0)
}

int knapsack(Integer[][] dp, int[] v, int[] w, int W, int n) {
    if (W <= 0 || n >= v.length) {
        return 0
    }
    if (dp[n][W]) {
        return dp[n][W]
    }
    int tryN = w[n] > W ? 0 : v[n] + knapsack(dp, v, w, W - w[n], n + 1)
    int skipN = knapsack(dp, v, w, W, n + 1)
    dp[n][W] = max(tryN, skipN)
}

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
[6, 8, 10].each {
    println "Total value for capacity $it = ${solve(values, weights, it)}"
}

为了解决背包问题，我们将它分解成更小的部分。如果我们已经缓存了对较小部分的解决方案，我们将使用缓存的值。由于我们构建问题的方式，我们实际上是在为不同的背包大小共享缓存的结果。

当我们运行此脚本时，它会产生以下输出

Total value for capacity 6 = 17
Total value for capacity 8 = 25
Total value for capacity 10 = 30

与大多数事情一样，在使用动态规划时，我们有多种选择。以下是一个替代变体，它保留一个第二个数组来跟踪所取的宝石

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
int W = 10
int N = values.length

int[][] dp = new int[N + 1][W + 1]
boolean[][] sol = new boolean[N + 1][W + 1]

for (int n = 1; n <= N; n++) {
    for (int w = 1; w <= W; w++) {
        int skipN = dp[n - 1][w]
        int tryN = weights[n - 1] > w ? 0 : values[n - 1] + dp[n - 1][w - weights[n - 1]]
        dp[n][w] = max(skipN, tryN)
        sol[n][w] = tryN > skipN
    }
}

println "Total value for capacity $W = ${dp[N][W]}"

def taken = []
for (int i = N, j = W; j > 0; i--) {
    if (sol[i][j]) {
        taken << i - 1
        j -= weights[i - 1]
    }
}
println "Gems taken: $taken"

如果我们只想计算出最终值，那么我们之前的变体将非常快，并且使用的内存更少。如果跟踪所取宝石很重要，那么此变体将是一种选择。

它产生以下输出

Total value for capacity 10 = 30
Gems taken: [3, 2, 1]

使用位集

在使用动态规划时，我们的二维 dp 数组对于大型问题可能会使用大量的内存。在这种情况下，我们可以使用位集而不是数组，如下所示

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
int W = 10
var N = weights.size()
var nums = 0L..<(1L << N)
var totalValue = nums
    .collect{ BitSet.valueOf(it) }
    .findAll{ mask -> mask.stream().map(idx -> weights[idx]).reduce(0, Integer::sum) <= W }
    .collect{ mask -> nums.indices.sum{ idx -> mask[idx] ? values[idx] : 0 } }
    .max()
println "Total value for capacity $W = $totalValue"

在这里，我们使用位集来跟踪候选解中的宝石组合。这可能看起来有点奇怪，但在我们的案例中可以完成任务。

它有以下输出

Total value for capacity 10 = 30

最常见的是，位集不仅用于节省内存，而且因为对于某些问题，我们可以对整个位集执行操作。可以将此视为与对布尔数组进行此类操作相比，具有免费并行性的批量操作。

我们可以通过添加一个初步的优化步骤来展示这种操作的一个简单示例。我们将使用一个简单的技巧，该技巧可以使用位移来查找一组数字的所有可能的总和。如果最大重量（在本例中为 10）不在可能的总和列表中 - 我们使用 maskW 常量找出这一点，然后我们丢弃该组合。为了简单起见，我们在这里保持示例简单，但请注意，这种粗略的优化有可能排除有效的候选者。理论上，最大值可能是重量为 8 或 9 的值。

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
int W = 10
var N = weights.size()
var maskW = 1L << W
var nums = 0L..<(1L << N)
var totalValue = nums
    .collect{ BitSet.valueOf(it) }
    .findAll{ mask -> mask.stream().reduce(1) {a, b -> a | a << weights[b] } & maskW }
    .findAll{ mask -> mask.stream().map(idx -> weights[idx]).reduce(0, Integer::sum) <= W }
    .collect{ mask -> nums.indices.sum{ idx -> mask[idx] ? values[idx] : 0 } }
    .max()
println "Total value for capacity $W = $totalValue"

对于此案例研究，它具有相同的输出，因此幸运的是，我们粗略的优化步骤没有拒绝最佳解决方案。

在本例中，我们只是移动了一个整数。根据具体的问题，我们可能希望改为移动一个长整数或位集。Groovy 5 为位集添加了对 <<（左移）、>>（右移）和 >>>（右移无符号）运算符的支持。这种功能将使使用 Groovy 处理此类问题变得更加方便。

使用约束编程

我们可以考虑的另一种技术是约束编程。在这里，我们定义一些约束，并让求解器为我们找到解决方案。在这里，我们使用了 Choco 求解器。

我们想通过说明什么是有界背包问题来丰富这个例子。现在，我们不再考虑将宝石要么取出，要么留下，而是将宝石视为随时可用的商品，重量和价值将适用于所有特定类型的宝石。

一般来说，我们可以根据需要获取任意类型的宝石（这将是无界的），或者像我们在这里做的那样，获取特定类型的宝石，直到某个界限为止。

在我们的示例中，我们将求解器的域变量的界限设置为 0 到 W 之间。我们可以轻松地将上限设置为 1，这样我们就回到了 0/1 背包问题。

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
int W = 10
int unbounded = 100000

var counts = new IntVar[values.length]
var found = false

new Model('KnapsackProblem').with {
    counts.indices.each(i -> counts[i] = intVar("count$i", 0, W))
    scalar(counts, weights, '<=', W).post()
    var total = intVar("Total value for capacity $W (unbounded)", 0, unbounded)
    scalar(counts, values, '=', total).post()
    setObjective(MAXIMIZE, total)

    while (solver.solve()) {
        found = true
        println "$total, $counts"
    }
}
if (!found) println 'No solution'

我们保留一个求解器变量数组 counts，对变量应用多个约束，并告诉求解器最大化 total 变量。

当我们运行此脚本时，它会产生以下输出

Total value for capacity 10 (unbounded) = 25, [count0 = 0, count1 = 5, count2 = 0, count3 = 0, count4 = 0]
Total value for capacity 10 (unbounded) = 30, [count0 = 0, count1 = 2, count2 = 2, count3 = 0, count4 = 0]
Total value for capacity 10 (unbounded) = 31, [count0 = 1, count1 = 0, count2 = 3, count3 = 0, count4 = 0]

在这里，求解器正在找到满足我们指定问题的解决方案，然后试图找到更好的解决方案。我们应该注意到，因为我们允许每种宝石不止一种，所以我们的答案 (31) 比我们之前的最佳答案 (30) 更高并不奇怪。

如果我们不想接收所有解决方案，我们可以简单地要求最佳解决方案，或者为求解器提供更好的搜索提示，以便更早地找到最佳答案。

事实证明，我们在这里设置的用来解决背包问题的约束集非常常见，以至于 Choco 有一个内置的 knapsack 方法，它可以为我们设置多个约束。我们可以按如下方式使用它

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
int W = 10
int unbounded = 100000

var counts = new IntVar[values.length]
var found = false

new Model('KnapsackProblem').with {
    counts.indices.each(i -> counts[i] = intVar("count$i", 0, W))
    var totalValue = intVar("Total value for capacity $W (unbounded)", 0, unbounded)
    var totalWeight = intVar("Total weight taken", 0, W)
    knapsack(counts, totalWeight, totalValue, weights, values).post()
    setObjective(MAXIMIZE, totalValue)

    while (solver.solve()) {
        found = true
        println "$totalValue, $totalWeight, $counts"
    }
}
if (!found) println 'No solution'

运行后，它将输出以下结果

Total value for capacity 10 (unbounded) = 30, Total weight taken = 10, [count0 = 0, count1 = 2, count2 = 2, count3 = 0, count4 = 0]
Total value for capacity 10 (unbounded) = 31, Total weight taken = 10, [count0 = 1, count1 = 0, count2 = 3, count3 = 0, count4 = 0]

使用 OrTools

其他库也具有用于背包的内置求解器。以下是使用 OrTools 库的另一个实现

Loader.loadNativeLibraries()
var solver = new KnapsackSolver(KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "knapsack")

long[] values = [1, 5, 10, 15, 17]
long[][] weights = [[1, 2, 3, 5, 6]]
long[] capacities = [10]

solver.init(values, weights, capacities)

long computedValue = solver.solve()
println "Total value for capacity ${capacities[0]} = " + computedValue

var packedItems = []
var packedWeights = []
int totalWeight = 0
values.indices.each { i ->
    if (solver.bestSolutionContains(i)) {
        packedItems << i
        packedWeights << weights[0][i]
        totalWeight += weights[0][i]
    }
}
println "Actual weight: $totalWeight"
println "Gems taken: $packedItems"
println "Gem weights: $packedWeights"

运行后，它将输出以下结果

Total value for capacity 10 = 30
Actual weight: 10
Gems taken: [1, 2, 3]
Gem weights: [2, 3, 5]

使用 Jenetics

我们也可以使用遗传算法来找到解决方案。当基于遗传算法创建解决方案时，会进行一系列模拟自然界进化的步骤。我们通常从一些随机猜测开始，我们将这些猜测视为第一代子代。我们有函数来测试个体的适应度，有过程根据当前一代选择新一代子代，有突变步骤等等。

我们将从创建一个记录来跟踪我们的权重和值开始。

record Item(int weight, int value) implements Serializable {}

我们将创建一个Knapsack类来跟踪状态并提供我们的适应度函数。

class Knapsack implements Problem<ISeq<Item>, BitGene, Integer> {
    private final Codec<ISeq<Item>, BitGene> codec
    private final double knapsackSize

    Knapsack(ISeq<Item> items, int knapsackSize) {
        codec = Codecs.ofSubSet(items)
        this.knapsackSize = knapsackSize
    }

    @Override
    Function<ISeq<Item>, Integer> fitness() {
        (items) -> {
            var sum = items.inject(new Item(0, 0)) { acc, next ->
                new Item(acc.weight + next.weight, acc.value + next.value)
            }
            sum.weight <= knapsackSize ? sum.value : 0
        }
    }

    @Override
    Codec<ISeq<Item>, BitGene> codec() { codec }
}

我们创建我们的遗传算法引擎并配置它，以找出下一代将如何选择，以及可能使用哪些突变（如果有）来提供随机更改。

我们还将创建一个log函数，以便在生成不同的代时输出一些信息。

以下是脚本

int W = 10
int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
var items = [weights, values].transpose().collect { w, v -> new Item(w, v) }
var iSeq = items.stream().collect(ISeq.toISeq())
var knapsack = new Knapsack(iSeq, W)

var engine = Engine.builder(knapsack)
    .populationSize(8)
    .survivorsSelector(new TournamentSelector<>(3))
    .offspringSelector(new RouletteWheelSelector<>())
    .alterers(
        new Mutator<>(0.1),
        new SinglePointCrossover<>(0.2),
        new MultiPointCrossover<>(0.1))
    .build()

var log = { EvolutionResult er ->
    var avg = er.population().average{ it.fitness() }
    var best = er.bestFitness()
    printf "avg = %5.2f, best = %d%n", avg, best
}

var best = engine.stream()
    .limit(bySteadyFitness(8))
    .limit(30)
    .peek(log)
    .collect(toBestPhenotype())

println best

运行时会产生此输出

avg = 18.88, best = 23
avg = 21.00, best = 25
avg = 22.00, best = 25
avg = 22.63, best = 25
avg = 25.63, best = 30
avg = 27.50, best = 30
avg = 27.63, best = 30
avg = 24.38, best = 30
avg = 22.50, best = 30
avg = 26.25, best = 30
avg = 30.00, best = 30
avg = 30.00, best = 30
[00001110] -> 30

由于它是随机的，因此后续运行可能会产生不同的结果。

avg = 16.75, best = 27
avg = 17.13, best = 23
avg = 18.00, best = 23
avg = 21.38, best = 27
avg = 24.00, best = 27
avg = 24.88, best = 27
avg = 22.50, best = 27
avg = 26.88, best = 27
[00010100] -> 27

正如我们在这里看到的那样，我们不能保证所有遗传算法问题都能得到最佳解决方案。

我们应该注意到，虽然该过程涉及各种随机方面，我们有时甚至可能真正杀死掉最佳个体，但如果我们正确配置了算法，我们应该看到平均适应度值和最佳适应度值随着时间的推移而上升。

使用贪婪选择

我们将要看的最后一个例子是“最优”或“贪心”解决方案。在这里，我们按照最佳价值/重量的顺序取物品。如果我们允许大于 1 的分数值，我们只需要使用此排序列表中的第一项，但在这里，任何项目的最大值为 1。

对于这个问题，与其说是宝石，宝石可能确实难以分割（或者至少分割后不会大幅贬值），不如说是异国香料，或其他可以轻松分割的贵重物品。

以下是代码

int[] values = [1, 5, 10, 15, 17]  // Gem values
int[] weights = [1, 2, 3, 5, 6]    // Weights
var ratios = values.indices.collect { values[it] / weights[it] }.withIndex().sort { -it[0] }
int W = 10
Map<Integer, BigDecimal> taken = [:]
var remaining = W
while (remaining && ratios) {
    var next = ratios.head()
    var index = next[1]
    if (remaining >= weights[index]) {
        taken[index] = 1
        remaining -= weights[index]
    } else {
        taken[index] = remaining / weights[index]
        break
    }
    ratios = ratios.tail()
}
var total = taken.collect{ index, qty -> values[index] * qty }.sum()
println taken
printf 'Total value for capacity %d (with fractions) = %6.3f%n', W, total

运行后，它将输出以下结果

[2:1, 3:1, 4:0.3333333333]
Total value for capacity 10 (with fractions) = 30.667

当允许贵重物品的分数数量时，我们可以获得大于 30 的值，这并不出乎意料。

更多信息

结论

我们已经了解了如何在 Groovy 中使用多种方法解决背包问题。在参考文献中，还有更多可以用来解决背包问题的奇异算法。如果您有使用 Groovy 解决背包问题的绝佳方法，请告诉我们，我们可以将其添加到此博客中！