java 完全背包问题

时间：2024-03-23 18:51:58

java 完全背包问题

问题描述

在完全背包问题中，给定一个背包的最大容量，和一系列物品，每种物品都有无限个可用，每个物品有自己的重量和价值。目标是在不超过背包容量的情况下，使得背包中物品的总价值最大。

与01背包的比较

在01背包问题中，每种物品只有一个可用，而在完全背包问题中，每种物品都有无限个可用。这意味着我们可以选择多次同一种物品放入背包中。

示例物品

假设背包的最大重量为6，且有以下物品：

  • 物品1：重量1，价值3
  • 物品2：重量3，价值2
  • 物品3：重量6，价值5

二维dp数组解决

解决思路

我们可以使用动态规划来解决完全背包问题。我们定义一个二维的动态规划数组 dp，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时的最大总价值。

状态转移方程

在状态转移方程中，我们需要考虑当前物品放入背包中的多种情况：

  • 如果不放入当前物品，则 dp[i][j] = dp[i-1][j]；
  • 如果放入当前物品，因为物品可以重复放入，我们可以选择多次放入当前物品直到超出背包容量，所以 dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i]] + values[i])。

初始化

我们需要对动态规划数组进行初始化，当没有物品时或背包容量为0时。

演算流程

物品\容量 0 1 2 3 4 5 6 7 8
无物品 0 0 0 0 0 0 0 0 0
物品1 0 2 4 6 8 10 12 14 16
物品1,2 0 2 4 6 8 10 12 14 16
物品1,2,3 0 2 4 6 8 10 12 14 16

Java代码

public class Bag01 {
    public int knapsack(int[] weight, int[] value, int capacity) {
        int n = weight.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        // 遍历物品
        for (int i = 1; i <= n; i++) {
            // 遍历背包承重
            for (int j = 1; j <= capacity; j++) {
                // 如果当前物品重量大于背包承重，无法放入背包
                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 取放入和不放入背包的最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
                    /*！！与01背包不同的地方在这里，放入物品时，不是使用dp[i - 1][j - weight[i - 1]]，
                    而是使用dp[i][j - weight[i - 1]]，表示可以重复选择当前物品*/
                }
            }
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }

        // 返回结果
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        Bag01 knapsack = new Bag01();
        int[] weight = {1, 3, 6};
        int[] value = {2, 5, 8};
        int capacity = 8;
        System.out.println("最大价值为: " +knapsack.knapsack(weight, value, capacity)); // 输出：16

    }
}

与01背包的不同

在完全背包问题中，与01背包问题不同之处在于，我们可以重复选择当前物品放入背包中，因此在更新状态时，如果选择放入当前物品，应该使用dp[i][j - weight[i - 1]]而不是dp[i - 1][j - weight[i - 1]]。

一维滚动数组解决（推荐）

Java代码

public class Main {
    // 定义一个方法，用于解决完全背包问题
    public static int knapsack(int[] weights, int[] values, int capacity) {
        // 获取物品数量
        int n = weights.length;
        // 创建一维数组，用于保存背包容量对应的最大价值
        int[] dp = new int[capacity + 1];// 数组大小定义记得是容量+1

        // 遍历每个物品
        for (int i = 0; i < n; i++) {
            // 逆序遍历背包容量，确保可以多次选择同一物品（与01背包不同）
            for (int j = weights[i]; j <= capacity; j++) {// 正序遍历，与01背包不同
                // 使用状态转移方程更新当前背包容量的最大价值
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        // 返回背包容量为capacity时的最大价值
        return dp[capacity];
    }

    public static void main(String[] args) {
        // 给定物品的重量和价值，以及背包的容量
        int[] weights = {1, 3, 6};
        int[] values = {2, 5, 8};
        int capacity = 8;

        // 调用knapsack方法计算最大价值
        int max_value = knapsack(weights, values, capacity);
        // 输出结果
        System.out.println("可以获得的最大价值：" + max_value);
    }
}

与01背包不同之处：

  1. 在遍历背包容量时，使用正序遍历（j 从 weights[i] 到 capacity），以确保可以多次选择同一物品放入背包中。
  2. 在状态转移方程中，不再需要判断背包容量是否大于等于物品重量，因为完全背包中可以多次选择同一物品。

相关文章