int main() { int C = 0;//背包总容量 int M = 0;//物品数目 cin >> C >> M; vector<thing> things;//物品 priority_queue<node> q;//搜索结点空间 //输入物品，并按单位价值从大到小排序 for (int i = 0; i < M; i++) { thing t; cin >> t.w >> t.v; things.push_back(t); things[i].getK(); } sort(things.begin(), things.end()); //开始搜索结点空间 node t; t.getUb(C, things, M); q.push(t); int result = 0;//最优解 while (q.empty() == false) { node f = q.top(); q.pop(); //得到最优解 if(f.V >= f.ub){ result = f.V; break; } //构造左结点（不选择-0） if (f.index < M) { node l = f; l.index = l.index + 1; l.getUb(C, things, M); q.push(l); } //构造右结点（选择-1） if (f.index < M && f.W + things[f.index].w <= C) { node r = f; r.W += things[r.index].w; r.V += things[r.index].v; r.a[r.index] = 1; r.index = r.index + 1; r.getUb(C, things, M); q.push(r); } } cout << result << endl; return 0; }

本题的解法是0/1背包问题的分支定界法，主要思路是利用优先队列来维护搜索结点空间，每次取出优先级最高的结点进行搜索，同时利用上界剪枝，减少搜索时间。具体解释见代码注释：

代码注释2：首先定义了物品类型 thing 和搜索树的结点 node，其中 thing 主要用于存储每个物品的质量、价值和单位价值比，以及计算单位价值比，便于排序和上界的计算。而 node 主要用于记录当前背包的质量和价值，以及当前的部分解和待决策结点，以及该结点的上界，便于后面进行剪枝。上界的计算采用贪心法，先将已经放入背包的物品按价值从大到小排序，然后从待决策结点开始，依次放入能放入背包的物品，直到放不下为止，最后将背包剩余的容量乘以单位价值最大的物品的单位价值，加上已经放入背包的物品的价值和，即为该结点的上界。

以下是将上述两段代码转换成Java的代码：

物品类型：

class Thing implements Comparable<Thing> {
    int w; // 物品的重量
    int v; // 物品的价值
    double k; // 物品的单位价值

    public Thing(int w, int v) {
        this.w = w;
        this.v = v;
        this.k = (double) v / w;
    }

    @Override
    public int compareTo(Thing o) {
        return Double.compare(o.k, this.k); // 按照单位价值从大到小排序
    }
}

搜索树的结点：

class Node implements Comparable<Node> {
    int W; // 当前背包的重量
    int V; // 当前背包的价值
    int ub; // 当前结点的上界
    int[] a; // 部分解
    int index; // 待决策结点

    public Node(int C, int M) {
        this.W = 0;
        this.V = 0;
        this.ub = 0;
        this.a = new int[M];
        this.index = 0;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(o.ub, this.ub); // 按照上界从大到小排序
    }

    // 计算上界
    public void getUb(int C, List<Thing> things) {
        int lb = 0; // 新放入物品的价值
        int _W = W;
        int i = index;

        // 贪心法按价值放能放的物品
        while (_W + things.get(i).w <= C && i < things.size()) {
            _W += things.get(i).w;
            lb += things.get(i).v;
            i++;
        }
        i++;

        int leave = (int) ((_W == C) ? 0 : (C - _W) * things.get(i).k);
        ub = V + lb + leave;
    }
}

注意，由于Java中没有结构体这个概念，因此我们将其转换成一个类，同时在构造函数中初始化了 a 数组，避免了在使用时的空指针异常。另外，由于Java中没有优先队列的比较器可以直接传入，因此在 Node 类中实现了 Comparable 接口，并重写了 compareTo 方法，以便在构造优先队列时进行排序。

完整的Java代码如下：

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int C = sc.nextInt(); // 背包总容量
        int M = sc.nextInt(); // 物品数目

        List<Thing> things = new ArrayList<>();
        PriorityQueue<Node> q = new PriorityQueue<>();

        // 输入物品，并按单位价值从大到小排序
        for (int i = 0; i < M; i++) {
            int w = sc.nextInt();
            int v = sc.nextInt();
            things.add(new Thing(w, v));
        }
        Collections.sort(things);

        // 开始搜索结点空间
        Node t = new Node(C, M);
        t.getUb(C, things);
        q.offer(t);

        int result = 0; // 最优解

        while (!q.isEmpty()) {
            Node f = q.poll();

            // 得到最优解
            if (f.V >= f.ub) {
                result = f.V;
                break;
            }
            // 构造左结点（不选择-0）
            if (f.index < M) {
                Node l = new Node(C, M);
                l.index = f.index + 1;
                l.W = f.W;
                l.V = f.V;
                l.a = Arrays.copyOf(f.a, f.a.length);
                l.getUb(C, things);
                q.offer(l);
            }
            // 构造右结点（选择-1）
            if (f.index < M && f.W + things.get(f.index).w <= C) {
                Node r = new Node(C, M);
                r.index = f.index + 1;
                r.W = f.W + things.get(f.index).w;
                r.V = f.V + things.get(f.index).v;
                r.a = Arrays.copyOf(f.a, f.a.length);
                r.a[f.index] = 1;
                r.getUb(C, things);
                q.offer(r);
            }
        }

        System.out.println(result);
    }
}

class Thing implements Comparable<Thing> {
    int w; // 物品的重量
    int v; // 物品的价值
    double k; // 物品的单位价值

    public Thing(int w, int v) {
        this.w = w;
        this.v = v;
        this.k = (double) v / w;
    }

    @Override
    public int compareTo(Thing o) {
        return Double.compare(o.k, this.k); // 按照单位价值从大到小排序
    }
}

class Node implements Comparable<Node> {
    int W; // 当前背包的重量
    int V; // 当前背包的价值
    int ub; // 当前结点的上界
    int[] a; // 部分解
    int index; // 待决策结点

    public Node(int C, int M) {
        this.W = 0;
        this.V = 0;
        this.ub = 0;
        this.a = new int[M];
        this.index = 0;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(o.ub, this.ub); // 按照上界从大到小排序
    }

    // 计算上界
    public void getUb(int C, List<Thing> things) {
        int lb = 0; // 新放入物品的价值
        int _W = W;
        int i = index;

        // 贪心法按价值放能放的物品
        while (_W + things.get(i).w <= C && i < things.size()) {
            _W += things.get(i).w;
            lb += things.get(i).v;
            i++;
        }
        i++;

        int leave = (int) ((_W == C) ? 0 : (C - _W) * things.get(i).k);
        ub = V + lb + leave;
    }
}

An error occurred with your deployment

EDGE_FUNCTION_INVOCATION_TIMEOUT