《0-1背包问题》贪心策略

假设我们有n种类型的物品，分别编号为1, 2...n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是Cap。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？

注意：每种物品只有一件，可以选择放或者不放。初始化数据为：n=5，w={2,2,6,5,4}，v={6,3,5,4,6}，Cap=10。

递推公式：

dp[ i ][ j ]：【0，i】物品任取放容量为j的背包。

不放物品i：dp[ i-1 ][ j ]

放物品i：dp[ i-1 ][ j - weight[ i ]] + value[ i ];

如果不放物品i，则当前的dp[ i ][ j ] = dp[ i-1 ][ j ];

如果放物品i：背包容量减去物品i的容量所能放的最大价值加上物品i的价值。

源代码如下：

import java.util.Scanner;

public class BackPackZeroOne {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //物品的数量
        int num = sc.nextInt();
        //背包最大重量
        int max = sc.nextInt();

        // 重量
        int[] weight = new int[num + 1];
        // 钱
        int[] value = new int[num + 1];
        //输入重量
        for (int i = 1; i <= num; i++) {
            weight[i] = sc.nextInt();
        }
        //输入价值
        for (int i = 1; i <= num; i++) {
            value[i] = sc.nextInt();
        }


        //创建num+1个背包，背包能承受的重量为max（0不包括，从1 开始）
        int[][] dp = new int[num + 1][max + 1];

        //dp[0]第一个背包什么都不装所以不遍历（全为0）;
        for (int i = 1; i <= num; i++) {
            //遍历背包容量
            for (int j = 1; j <= max; j++) {
                //当前共有i个物品
                //如果当前的背包承受重量 j 大于第 i 个物品的重量，
                if (i > 0 && weight[i] <= j) {
                    //那么对比上一个背包的当前背包承受重量的最大值 和 上一个背包减去当前 i 物品的重量weight[i]，并加上 i 物品的价值value[i]，
                    //就相当于把上个背包承受重量减去 i 的重量，这样就刚刚能放下 i 物品，
                    //因为放下了 i 物品，所以需要加上 i 物品的价值。
                    //添加 i 物品和不添加 i 物品的价值对比。
                    if ((dp[i - 1][j - weight[i]] + value[i]) < dp[i - 1][j]) {
                        //如果不添加i物品的价值最大的话，那么当前的背包数量等于不添加物品的价值
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        //如果添加 i 物品的价值大的话那么当前j背包数量的价值就等于添加i物品后的价值。
                        dp[i][j] = dp[i - 1][j - weight[i]] + value[i];
                    }
                } else {
                    //如果当前背包装不下i物品那么当前背包价值等于上一个背包当前重量的价值。
                    dp[i][j] = dp[i - 1][j];
                }
                /**
                 * 输出一行背包
                 */
                System.out.printf("%-5d", dp[i][j]);

            }
            /**
             * 控制台输出换行
             */
            System.out.println();
        }
        System.out.println(dp[num][max]);
    }
}

打印结果如下所示：

其中有5列十行，行对应着物品i，从1到5 。

列对应着背包的容量，从1到10。

最下面对应的取dp数组的最大值即背包所能装物体的最大价值。