本文共 1916 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到一种方法来选择背包中的物品，使得总体积不超过背包容量，并且总价值最大。这个问题类似于0-1背包问题，但每个物品来自不同的组，每组只能选择一个物品。

方法思路

解决代码

import java.io.*;import java.util.*;class Main {    static int[] dp = new int[1001];    static int n = 0, m = 0;    static List
   
     items = new ArrayList<>();    public static void main(String[] args) throws Exception {        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));        String[] params = buf.readLine().split(" ");        n = Integer.parseInt(params[0]);        m = Integer.parseInt(params[1]);        for (int i = 1; i <= n; ++i) {            int cnt = Integer.valueOf(buf.readLine());            for (int j = 1; j <= cnt; ++j) {                String[] info = buf.readLine().split(" ");                int a = Integer.valueOf(info[0]);                int b = Integer.valueOf(info[1]);                items.add(new int[]{a, b});            }        }        // 排序物品，按体积升序        Collections.sort(items, new Comparator
    
     () {            public int compare(int[] a, int[] b) {                return Integer.compare(a[0], b[0]);            }        });        // 初始化动态规划数组        Arrays.fill(dp, 0);        for (int[] item : items) {            int v = item[0];            int w = item[1];            if (v > m) continue;            for (int j = m; j >= v; --j) {                if (dp[j - v] + w > dp[j]) {                    dp[j] = dp[j - v] + w;                }            }        }        System.out.println(dp[m]);    }}
    
   

代码解释

这种方法确保了每个物品只被处理一次，并且通过动态规划高效地更新背包状态，能够在合理时间内解决问题。

转载地址：http://zyre.baihongyu.com/