带容量限制的双数组最大总价值求解问题

问题说明 #

现有两个数组，capacity数组与price数组的下标一一对应，对应位置分别表示单个物品的占用容量和对应价值，数组定义如下：

int[] price = {60, 120, 100, 100, 30, 20};
int[] capacity = {1, 3, 2, 2, 3, 1};

需要在给定总容量上限的约束下，计算可获得的最大总价值，实现求解函数func(price, capacity, capacityRestriction)。

官方测试用例参考：

调用func(price, capacity, 6)时返回值为280，为总容量上限为6时的最高总价格。

实现思路 #

这是典型的0-1背包问题，每个物品仅可选择一次，使用动态规划求解即可：

• 定义dp数组，dp[i]表示容量为i时可获得的最大价值
• 遍历每个物品，倒序更新dp数组避免重复选取同一个物品
• 最终dp[capacityRestriction]就是所求的最大价值

参考代码（Java版本） #

public class KnapsackSolution {
    public static int func(int[] price, int[] capacity, int capacityRestriction) {
        int[] dp = new int[capacityRestriction + 1];
        // 遍历每个物品
        for (int i = 0; i < price.length; i++) {
            int curPrice = price[i];
            int curCap = capacity[i];
            // 倒序遍历容量，防止重复选同一物品
            for (int j = capacityRestriction; j >= curCap; j--) {
                dp[j] = Math.max(dp[j], dp[j - curCap] + curPrice);
            }
        }
        return dp[capacityRestriction];
    }

    public static void main(String[] args) {
        int[] price = {60, 120, 100, 100, 30, 20};
        int[] capacity = {1, 3, 2, 2, 3, 1};
        // 测试用例，输出280
        System.out.println(func(price, capacity, 6));
    }
}

代码验证 #

上述代码运行测试用例时输出结果为280，和要求的返回值一致，逻辑正确。

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