用java并使用分支限界法求解01背包问题

Question

用java并使用分支限界法求解01背包问题
实验目的：分支限界法按广度优先策略遍历问题的解空间树，在遍历过程中,对已经处理的每一个结点根据限界函数估算目标函数的可能取值，从中选取使目标函数取得极值的结点优先进行广度忧先搜索，从而不断调整搜索方向，尽快找到问题的解。因为限界函数常常是基于向题的目标函数而确定的，所以，分支限界法适用于求解最优化问题。本次实验利用分支限界法解决0-1背包问题。
实验内容：运用分支限界法解决0-1背包问题。
0-1背包问题1基本思想：
给定n种物品和一个容量为C的背包。物品i的重量是W，其价值为V, 0/ 1背包问题是如何选择装入背包的物品(物品不可分割)，使得装入背包中物品的总价值最大，一般情况下，解空间树中第i层的每个结点，都代表了对物品1--i做出的某种特定选择，这个特定选择由从根结点到该结点的路径唯一确定:左分支表示装入物品，右分支表示不装入物品。对于第i层的某个结点, 假设背包中已装入物品的重量是w，获得的价值是v,计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v，加上背包剩余容量W- w与剩下物品的最大单位重量价值Vi+1/Wi +1的积,于是,得到限界函数:
U b= v +(W —w)× ( vi+1 /wi +l)
根据限界函数确定目标函数的界[ down , up]，然后，按照广度优先策略遍历问题的空间树。

Answer 1

import java.util.PriorityQueue;  
  
class Node implements Comparable<Node> {  
    int level; // 当前层级  
    int weight; // 当前重量  
    int value; // 当前价值  
    int bound; // 上界  
  
    public Node(int level, int weight, int value, int bound) {  
        this.level = level;  
        this.weight = weight;  
        this.value = value;  
        this.bound = bound;  
    }  
  
    @Override  
    public int compareTo(Node other) {  
        // 按照bound的降序排列  
        return other.bound - this.bound;  
    }  
}  
  
public class Knapsack {  
    int capacity; // 背包容量  
    int n; // 物品数量  
    int[] weights; // 物品重量  
    int[] values; // 物品价值  
  
    public Knapsack(int capacity, int n, int[] weights, int[] values) {  
        this.capacity = capacity;  
        this.n = n;  
        this.weights = weights;  
        this.values = values;  
    }  
  
    public int maxValue() {  
        // 初始化优先队列  
        PriorityQueue<Node> queue = new PriorityQueue<>();  
        queue.add(new Node(0, 0, 0, bound(0, 0)));  
        int maxValue = 0;  
  
        while (!queue.isEmpty()) {  
            Node node = queue.poll(); // 取出队首元素  
            if (node.level == n) { // 达到叶子节点，更新最大值  
                maxValue = Math.max(maxValue, node.value);  
            } else {  
                // 左子树：选择当前物品  
                if (node.weight + weights[node.level] <= capacity) {  
                    queue.add(new Node(node.level + 1, node.weight + weights[node.level],   
                                       node.value + values[node.level], bound(node.level + 1, node.weight + weights[node.level])));  
                }  
                // 右子树：不选择当前物品  
                queue.add(new Node(node.level + 1, node.weight, node.value, bound(node.level + 1, node.weight)));  
            }  
        }  
        return maxValue;  
    }  
  
    // 计算上界函数  
    private int bound(int i, int weight) {  
        int remainingWeight = capacity - weight; // 剩余重量  
        int remainingValue = 0; // 剩余价值  
        for (int j = i; j < n; j++) {  
            if (weights[j] > remainingWeight) { // 当前物品装不下，跳出循环  
                break;  
            }  
            remainingWeight -= weights[j]; // 减去当前物品的重量  
            remainingValue += values[j]; // 加上当前物品的价值  
        }  
        return remainingValue + (remainingWeight / (double) weights[n - 1]) * values[n - 1]; // 返回上界值，注意这里使用了double类型进行除法运算来保留小数部分的价值  
    }  
}