提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

动态规划01 背包问题（算法）

2023-02-18 16:29:02 时间

上篇文章说了，查找组成一个偶数最接近的两个素数算法：

查找组成一个偶数最接近的两个素数（算法）

本篇文章题目是 动态规划01 背包问题：

背包容量5kg，现在有三个物体，分别是重量是1 价值是 6、重量是2价值是10，重量是4价值是12。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出最大价值。

解题思路：

定义dp二级数组，一级放入是物体个数，二级放入是背包实际重量。

第一行代表只放1kg的时候，分别对应物体放入的价值。

第二行代表只放2kg的时候，分别对应物体放入的价值，依次类推。

先循环物体个数。

再循环实际背包重量。

只有当前背包容量大于等于当前物品的价值 才放入二级数组。

此时物品的价值和减去该价值物品的重量的价值。

如果不能装入的话则把上一行的价值赋值。

/**
     * 背包5kg，物品为三个，
     * {1,2,4} 重量
     * {6,10,12}价值
     * dp 行代表物品，列代表容量。
     */
    public static void main(String[] args) {
        int[] value = {6, 10, 12};
        int[] weight = {1, 2, 4};
 
        int wu = 3;
        int kg = 5;
 
        int[][] dp = new int[wu + 1][kg + 1];
 
        for (int i = 1; i <= wu; i++) {
            for (int j = 1; j <= kg; j++) {
                if (weight[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
                } else {
                    // 放入上一列的
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
 
        for (int i = 1; i <= wu; i++) {
            System.out.print("第"+i+"个物品"+"      ");
            for (int j = 1; j <= kg; j++) {
                System.out.print(dp[i][j]+"      ");
            }
            System.out.println("");
        }
 
        System.out.println(dp[wu][kg]);
    }
 
 
 public static void main(String[] args) {
        int[][] wp = new int[3][2];
        wp[0][0] = 1;
        wp[0][1] = 6;
        wp[1][0] = 2;
        wp[1][1] = 10;
        wp[2][0] = 4;
        wp[2][1] = 12;
 
        int[] dp = new int[5 + 1];
   
        for (int i = 0; i < 3; i++) {
            // 当前 物体重量 小于等于 背包重量
            for (int j = dp.length - 1; j >= wp[i][0]; j--) {
                dp[j] = Math.max(dp[j], dp[j - wp[i][0]] + wp[i][1]);
            }
        }
        System.out.println(dp[dp.length - 1]);
    }

相关文章