完全背包问题

问题描述

有n种物品，每种物品有无限个，每个物品的重量为weight[i]，每个物品的价值为value[i]。 现在有一个背包，它所能容纳的重量为total，问：当你面对这么多有价值的物品时，你的背包所能带走的最大价值是多少？

• n:物品数量
• weight[] :每个物品的重量
• value[]: 每个物品的价值
• total:背包的最大承重

实现原理

完全背包问题和之前的 01背包问题思路是类似的,只不过完全背包问题中对每个物品的数量没有了限制,可以无限使用。这里直接使用最优解的方法做了，如果你对如何从普通解到最优解的转换还不熟悉，请参考 01背包问题；

使用一个dp[n][total+1]数组,其中dp[j]表示在背包最大承重为j的情况下的最优解. 那么dp[i][j]的值如何确定呢?

首先:确定当前最大的承重是j,那么用不用物品i呢?

如果不使用i,那么dp[i][j] = dp[i-1][j]

如果使用i,那么dp[i][j] = dp[i][j-w[i]]+v[i]

初步实现

void f1() {
  //开始套路
  int n;  //一共有n件物品
  int total; //背包的总重量为total

  n = 5;
  total = 10;

  int[] w = {4, 5, 6, 2, 2};
  int[] v = {6, 4, 5, 3, 6};

  int[][] dp = new int[n][total + 1];

  //初始化第一行
  for (int i = w[0]; i < total + 1; i++) {
    dp[0][i] = dp[0][i - w[0]] + v[0];
  }

  //第一列就不初始化了吧


  for (int i = 1; i < n; i++) {
    for (int j = 0; j < total + 1; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= w[i]) {
        dp[i][j] = Math.max(dp[i][j], dp[i][j - w[i] + v[i]]);
      }
    }
  }
  System.out.println(dp[n-1][total]);
}

压缩空间

void f2() {
    //开始套路
    int n;  //一共有n件物品
    int total; //背包的总重量为total

    n = 5;
    total = 10;

    int[] w = {4, 5, 6, 2, 2};
    int[] v = {6, 4, 5, 3, 6};

    int[] dp = new int[total + 1];

    //初始化第一行
    for (int i = w[0]; i < total + 1; i++) {
        dp[i] = dp[i - w[0]] + v[0];
    }


    for (int i = 1; i < n; i++) {
        for (int j = 0; j < total + 1; j++) {
            if (j >= w[i]) {
                dp[j] = Math.max(dp[j], dp[j - w[i] + v[i]]);
            }
        }
    }
    System.out.println(dp[total]);
}

其实这里面的初始化第一行不是必须的,直接进行下面的for循环也是可以的,只需要把外层for的初始值改为0即可;我这里只不过是习惯了写动态规划的套路,在这样做的,如果你喜欢更简洁的写法,请看下面.

更简洁的写法

改进后的代码如下:

void f3() {
    //开始套路
    int n;  //一共有n件物品
    int total; //背包的总重量为total

    n = 5;
    total = 10;

    int[] w = {4, 5, 6, 2, 2};
    int[] v = {6, 4, 5, 3, 6};

    int[] dp = new int[total + 1];


    for (int i = 0; i < n; i++) {
        for (int j = w[i]; j < total + 1; j++) {
            dp[j] = Math.max(dp[j], dp[j - w[i] + v[i]]);
        }
    }
    System.out.println(dp[total]);
}

完全背包问题的变形问题

最小钱币数

给定一个数组arr,该数组中的各个数代表钱币的面值,每个面值的数量无限多, 给定一个aim,用arr中的钱币凑齐aim数,是的凑出的钱币数量最少

直接上代码:

public static int minCoins1(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return -1;
    }
    int n = arr.length;
    int max = Integer.MAX_VALUE;

    //(1)构造动态数组 (2)此时的数组其实已经初始化为全0了;
    int[][] dp = new int[n][aim + 1];  //n行,aim+1列;此时的列的索引就是当前凑的货币总额;

    //(2)初始化第一行;
    for (int j = 1; j <= aim; j++) {  //此时j就是当前行的钱币凑成的总额;注意是从1开始的,也就是说第0列的值为0;
        dp[0][j] = max;//先赋值为max;
        //第一个判定条件是保证第二个判定条件数组下标不越界
        //只是初始化第一行,将arr[0]的倍数列初始化响应的倍数;
        if (j - arr[0] >= 0 && dp[0][j - arr[0]] != max) {
            dp[0][j] = dp[0][j - arr[0]] + 1;
        }
    }

    int left = 0;
    for (int i = 1; i < n; i++) {//最外层按列遍历
        for (int j = 1; j <= aim; j++) {//内层按行遍历
            left = max;
            //判断j是不是>arr[i],并且第j-arr[i]列不是max
            if (j - arr[i] >= 0 && dp[i][j - arr[i]] != max) {
                left = dp[i][j - arr[i]] + 1;
            }
            //这一步,比较left和上一行的大小才进行真正的数组初始化;
            dp[i][j] = Math.min(left, dp[i - 1][j]);
        }
    }
    return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
}

压缩空间的方法:

//最简洁的写法;
 public static int f1(int[] arr, int aim) {
     //创建数组
     int[] dp = new int[aim + 1];
 
     //初始化第一行
     int max = Integer.MAX_VALUE;
     for (int i = 1; i < aim + 1; i++) {
         dp[i] = max;
         if (i >= arr[0] && dp[i - arr[0]] != max) {
             dp[i] = dp[i - arr[0]] + 1;
         }
     }
 
     for (int i = 1; i < arr.length; i++) {
         for (int j = arr[i]; j < aim + 1; j++) {
             if (dp[j - arr[i]] != max) {
                 dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
             }
         }
     }
     return dp[aim] != max ? dp[aim] : -1;
 }

换钱币的方法数

上一题是求最少钱币的数量,现在是让求有几种可以换算的方法(每种钱币数量无限)之前我们所有的动态规划目标都是一个:求最优解,现在让求的是所有的解的个数

直接上代码

public static int f1(int[] arr, int aim) {

    int[] dp = new int[aim + 1];

    //初始化第一行
    for (int i = 0; i < aim + 1; i += arr[0]) {
        dp[i] = 1;
    }

    for (int i = 1; i < arr.length; i++) {
        for (int j = arr[i]; j < aim+1; j++) {
            dp[j] += dp[j - arr[i]];
        }
    }

    return dp[aim];
}

这里需要注意的点是:需要把第0列初始化为1,而不是0;