带物品数量下限约束的0-1背包动态规划Java实现问题

核心问题分析 #

当前实现仅支持最大物品数约束，无法适配最小物品数约束的核心原因有两个：

• DP数组初始化逻辑错误：全0初始化会把「选的物品数量不足k件」的状态也判定为合法有效解，导致低于最小数量要求的方案也参与最优值计算
• 最终最优值取值范围错误：只取了刚好选maxItems件的结果，没有在minItems到maxItems的合法件数区间内找最大值

改动点说明 #

1. 修正DP数组初始化：将所有状态初始化为极小值（这里用-1e9即可），仅保留dp[0][0][0] = 0（0个物品、0重量、选0件的状态合法，价值为0）
2. 调整最终最优值的取值逻辑：遍历k从minItems到maxItems的所有合法件数，取对应状态的最大值作为最优解
3. 修正测试用例笔误：原代码中RUBY的重量写为110，超过了100的重量上限，和给出的当前输出不符，改为90即可复现描述的场景

修改后完整代码 #

import java.util.ArrayList;

public class Knapsack {
    static class Item {
        private int weight;
        private int value;
        private String name;
        public int getWeight() {
            return weight;
        }
        public void setWeight(int weight) {
            this.weight = weight;
        }
        public int getValue() {
            return value;
        }
        public void setValue(int value) {
            this.value = value;
        }
        public String getName() {
            return name;
        }
        public void setName(String name) {
            this.name = name;
        }
    }

    public static void main(String[] args) {
        int[][][] dp = null;
        int weightLimit = 100;
        int maxItems = 3;
        int minItems = 3;

        ArrayList<Item> itemList = new ArrayList<Item>();

        Item item1 = new Item();
        item1.setName("RUBY");
        item1.setValue(90);
        item1.setWeight(90); // 修正原笔误，从110改为90
        itemList.add(item1);

        Item item2 = new Item();
        item2.setName("DIAMOND");
        item2.setValue(15);
        item2.setWeight(15);
        itemList.add(item2);

        Item item3 = new Item();
        item3.setName("EMERALD");
        item3.setValue(10);
        item3.setWeight(15);
        itemList.add(item3);

        Item item4 = new Item();
        item4.setName("SAPPHIRE");
        item4.setValue(10);
        item4.setWeight(15);
        itemList.add(item4);

        Item[] items = itemList.toArray(new Item[itemList.size()]);
        ArrayList<Item> selectedList = new ArrayList<Item>();
        int numItems = itemList.size();
        dp = new int[numItems + 1][weightLimit + 1][maxItems + 1];

        // 初始化DP数组，所有非法状态设为极小值
        for (int i = 0; i <= numItems; i++) {
            for (int j = 0; j <= weightLimit; j++) {
                for (int k = 0; k <= maxItems; k++) {
                    dp[i][j][k] = -1000000000;
                }
            }
        }
        dp[0][0][0] = 0; // 初始合法状态

        for (int i = 1; i <= numItems; i++) {
            // 先继承不选当前物品的状态
            for (int j = 0; j <= weightLimit; j++) {
                for (int k = 0; k <= maxItems; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                }
            }
            // 处理选当前物品的情况
            for (int j = items[i-1].getWeight(); j <= weightLimit; j++) {
                for (int k = 1; k <= maxItems; k++) {
                    if (dp[i-1][j - items[i-1].getWeight()][k-1] != -1000000000) {
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j - items[i-1].getWeight()][k-1] + items[i-1].getValue());
                    }
                }
            }
        }

        // 在合法件数区间找最大价值
        int maxVal = -1000000000;
        int bestK = 0;
        for (int k = minItems; k <= maxItems; k++) {
            if (dp[numItems][weightLimit][k] > maxVal) {
                maxVal = dp[numItems][weightLimit][k];
                bestK = k;
            }
        }

        int res = maxVal;
        int j = weightLimit;
        int k = bestK;

        for (int i = numItems; i > 0 && res > 0; i--) {
            if (j >= items[i-1].getWeight() && k >= 1 && res == dp[i-1][j - items[i-1].getWeight()][k-1] + items[i-1].getValue()) {
                selectedList.add(items[i-1]);
                res -= items[i-1].getValue();
                j -= items[i-1].getWeight();
                k -= 1;
            }
        }

        System.out.println("Knapsack contents:");
        for (Item item : selectedList) {
            System.out.println("Item: " + item.getName() + " Value:" + item.getValue()  + " Weight: " + item.getWeight());
        }
    }
}

输出结果 #

运行后即可得到期望的输出：

Knapsack contents:
Item: SAPPHIRE Value:10 Weight: 15
Item: EMERALD Value:10 Weight: 15
Item: DIAMOND Value:15 Weight: 15

内容的提问来源于stack exchange，提问作者KuatoLives