一 问题描述

二 算法设计

本问题为 01 背包问题，可以采用子集树。约束函数为 cw+w[i]<=m，其中 w[i] 为第 i 个物品的重量，m 为背包容量。限界函数 cp+brp>best，其中，cp 表示当前装入背包的物品价值，brp 表示剩余容量可容纳的剩余物品的最大价值，bestp 表示当前最优值。

三 代码

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

public class Poj3624 {
    public String output = "";
    private final int M = 105;
    int i, j;
    int n; // n 表示 n 个装饰物
    int W; // W 表示装饰物的总重量
    int w[] = new int[M]; // w[i] 表示第 i 个装饰物的重量
    int v[] = new int[M]; // v[i] 表示第 i 个装饰物的期望值
    boolean x[] = new boolean[M]; // x[i] 表示第 i 个装饰物是否可用于装饰
    int cw;  // 当前重量
    int cp;  // 当前期望值
    int bestp;  // 当前最优期望值

    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] = Integer.parseInt(weightAndValue[0]);
            v[i] = Integer.parseInt(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) { // 已经到达叶子结点
            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;
        // 用来统计所有装饰物的总期望值
        int sumv = 0;
        for (i = 1; i <= n; i++) {
            sumv += v[i];
            sumw += w[i];
        }
        if (sumw <= W) {
            bestp = sumv;
            output = bestp + "";
            return;
        }
        Backtrack(1);
        output = bestp + "";
    }
}

四 测试