一 问题描述

假设有 n 个物品和 1 个背包，每个物品的 i 对应的价值为 vi，重量为 wi，背包容量为 W。每个物品只有一件，要么装入，要么不装入，不可拆分。如何选择物品装入背包，使背包所装入的物品的总价值最大？要求输出最优值和最优解。

二 问题分析

从 n 个物品中选择一些物品，相对于从 n 个物品组成的集合 S 中找到一个子集，这个子集内所有物品的总重量不超过背包容量，并且这些物品的总价值最大。S 的所有子集都是问题的可能解，这些可能解组成解空间。我们在解空间中找总重量不超过背包容量且价值最大的物品集作为最优解。这些由问题的子集组成的解空间，其解空间树被称为子集树。

三 图解

物品的重量和价值分别保存到数组 w[] 和 v[] 中，w[] = {2,5,4,2}，v[] = {6,3,5,4},背包容量为10。

该问题的搜索路径如下：1 2 3 4 5 4 3 2 6 7 8 7 5 2 1

四 代码

package com.platform.modules.alg.alglib.p922;

public class P922 {
    public String output = "";
    private final int M = 105;
    int i, j;
    int n; // n 表示 n 个物品
    int W; // W 表示背包的容量
    double w[] = new double[M]; // w[i] 表示第 i 个物品的重量
    double v[] = new double[M]; // v[i] 表示第 i 个物品的价值
    boolean x[] = new boolean[M]; // x[i] 表示第 i 个物品是否放入背包
    double cw;  // 当前重量
    double cp;  // 当前价值
    double bestp;  // 当前最优价值
    boolean bestx[] = new boolean[M]; // 当前最优解

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] word = line[0].split(" ");
        n = Integer.parseInt(word[0]);
        W = Integer.parseInt(word[1]);

        for (i = 1; i <= n; i++) {
            String[] weightAndValue = line[i].split(" ");
            w[i] = Double.parseDouble(weightAndValue[0]);
            v[i] = Double.parseDouble(weightAndValue[1]);
        }
        Knapsack(W, n);
        return output;
    }

    // 计算上界（即已装入物品价值 + 剩余物品的总价值）
    double Bound(int i) {
        // 剩余物品为第 i~n 种物品
        int rp = 0;
        while (i <= n) { // 依次计算剩余物品的价值
            rp += v[i];
            i++;
        }
        return cp + rp;
    }

    // 用于搜索空间数，t 表示当前扩展结点在第t层
    void Backtrack(int t) {
        if (t > n) { // 已经到达叶子结点
            for (j = 1; j <= n; j++)
                bestx[j] = x[j];
            bestp = cp;//保存当前最优解
            return;
        }
        if (cw + w[t] <= W) { // 如果满足约束条件则搜索左子树
            x[t] = true;
            cw += w[t];
            cp += v[t];
            Backtrack(t + 1);
            cw -= w[t];
            cp -= v[t];
        }
        if (Bound(t + 1) > bestp) { // 如果满足限界条件则搜索右子树
            x[t] = false;
            Backtrack(t + 1);
        }
    }

    void Knapsack(double W, int n) {
        // 初始化当前放入背包的物品重量为 0
        cw = 0;
        // 初始化当前放入背包的物品价值为 0
        cp = 0;
        // 初始化当前最优值为0
        bestp = 0;
        // 用来统计所有物品的总重量
        double sumw = 0.0;
        // 用来统计所有物品的总价值
        double sumv = 0.0;
        for (i = 1; i <= n; i++) {
            sumv += v[i];
            sumw += w[i];
        }
        if (sumw <= W) {
            bestp = sumv;
            output = bestp + "\n";
            output += "所有的物品均放入背包。";
            return;
        }
        Backtrack(1);
        output = bestp + "\n";
        for (i = 1; i <= n; i++) { // 输出最优解
            if (bestx[i] == true)
                output += i + " ";
        }
    }
}

五 测试