01背包问题

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

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

实现原理

使用一个dp[n + 1][weight + 1]数组,其中dp[i][j]表示如果背包重量是j的情况下,使用前i个物品的最优解,

那么dp[i][j]的值如何确定呢?

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

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

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

所以dp[i][j]的值就是上述两者的最大值;

初步实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static void f1() {  
  Scanner in = new Scanner(System.in);  
  while (in.hasNext()) {  
    int n = in.nextInt();  //背包数量;
    int weight = in.nextInt();  //重量;
    int[] v = new int[n + 1];  //value;
    int[] w = new int[n + 1];  //weight;
//我们这里都是用了一个+1的操作,就是说不从0开始计算了,而是从1开始计算,这样更容易理解吧;
    int[][] res = new int[n + 1][weight + 1];  //结果集;

    for (int i = 1; i <=n; i++) {  
      w[i] = in.nextInt();  
      v[i] = in.nextInt();  
    }

    //初始化第一列
    for (int i = 1; i <=n; i++) {  
      res[i][0] = 0;  
    } 
    
    //初始化第一行;
    for (int j = 0; j <=weight; j++) {  
      res[0][j] = 0;  
    } 

	//开始规划
    for(int i=1;i<=n;i++) {  
      for (int j = 1; j <= weight; j++) {  //这里k代表的是当前背包的重量;
        res[i][j] = res[i - 1][j];    //不用当前j

        if (j >= w[i]) {  //当前包的重量小于j,考虑很周到,如果当前包重量过大,也是不行的...
          if (res[i-1][j - w[i]] + v[i] > res[i-1][j])  //用当前i比不用更大,那么就用上;
          {  
            res[i][j] = res[i-1][j - w[i]] + v[i];    //使用当前i;
          }     
        }  
      }  
    }  
    System.out.println(res[n][weight]);  
  }  
  in.close();  
}

压缩空间

上面的实现方法用了一个二维数组,其实完全可以用一个一维数组来代替;

这里有一个要注意的地方:编程思路和上面是一样的,也是两层循环,只不过现在从二维变成了一维,可是我们需要dp[i][j] = dp[i-1][j-w[i]]+v[i]的情况,如果内层循环也是从1开始计数的话,前面的值就被覆盖了,后面的值依赖前面的值,所以内层循环从右到左开始循环;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void f2() {  
  Scanner in = new Scanner(System.in);  
  while (in.hasNext()) {  
    int n = in.nextInt();  //背包数量
    int weight = in.nextInt();  //背包承重

    int[] v = new int[n + 1];  //values;
    int[] w = new int[n + 1];  //weights;
    int[] res = new int[weight + 1];  //结果集

    for (int i = 1; i <=n; i++) {  
      w[i] = in.nextInt();  
      v[i] = in.nextInt();  
    }  


    for(int i=1;i<=n;i++) {  
      for (int k = weight; k>=0; k--) {  
        if (w[i] <= k) {  
          if (v[i] + res[k - w[i]] > res[k])  
          {  
            res[k] = v[i] + res[k - w[i]];  
          }  

        }  
      }  
    }  
    System.out.println(res[weight]);  
  }  
  in.close();  
}

一个更简洁的写法

注意传入进来的v和w是从0开始的,不是从1开始的了;上面使用的从1开始只是为了方便的说明问题,现在v和w都是从0开始的,只是res结果集还是使用的total+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int f3(int[] values, int[] weights, int maxWeight) {
 
  int[] res = new int[maxWeight + 1];  //动态规划数组;
  
  for (int i = 0; i < values.length; i++) {  //遍历到第i个物品;
    for (int j = maxWeight; j >= weights[i]; j--) {  //内层循环倒着来;注意人家的终止条件啊;
      int takeValue = values[i] + res[j - weights[i]];  //使用当前i
      if (takeValue > res[j]) {  //使用当前i的时候如果比不使用的时候大,那么将res[j]的位置替换成使用的情况;
        res[j] = takeValue;
      }
    }
  }
  
  return res[ans.length - 1];
}

01背包的一个变形问题

给定一个物品数组,每个物品都有一个价值,每个物品数量为1,再得定一个整数aim代表期望的价值,求组成aim的最小物品数量,如果组不成,那么返回-1;

使用二维数组的做法

dp[i][j]代表的是aim=j的情况下,使用前面i种钱币的最优解;那么在接下来的规划中如何做呢?

首先我们是把数组中的每个元素都初始化为Integer.MAX_VALUE了,那么j的情况下,考虑能不能使用i,如果dp[i-1][j-v[i]]不是最大值,那么就可以用上j,否则赋值为dp[i-1][j];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static int f4(int[] arr, int aim) {
  if (arr == null || arr.length == 0 || aim < 0) {
    return -1;
  }
  int n = arr.length;
  int max = Integer.MAX_VALUE;
  int[][] dp = new int[n][aim + 1]; //创建dp数组

  //和之前一样,初始化数组的第一行
  for (int j = 1; j <= aim; j++) {
    dp[0][j] = max;
  }
  //只给恰好等于的元素置为1;
  if (arr[0] <= aim) {
    dp[0][arr[0]] = 1;
  }

  int leftup = 0; // 左上角某个位置的值

  for (int i = 1; i < n; i++) { //最外层从上到下遍历
    for (int j = 1; j <= aim; j++) { //最内层从左到右遍历
      leftup = max;
      if (j - arr[i] >= 0 && dp[i - 1][j - arr[i]] != max) { //现在是上一行的,有值才赋值=>保证只使用一次;
        leftup = dp[i - 1][j - arr[i]] + 1;
      }
      dp[i][j] = Math.min(leftup, dp[i - 1][j]);
    }
  }
  return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
}

使用一维数组的做法

注意内层循环依然使用从右到左的方式;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int f5(int[] arr, int aim) {
  if (arr == null || arr.length == 0 || aim < 0) {
    return -1;
  }
  int n = arr.length;
  int max = Integer.MAX_VALUE;
  int[] dp = new int[aim + 1];
  for (int j = 1; j <= aim; j++) {
    dp[j] = max;
  }
  if (arr[0] <= aim) {
    dp[arr[0]] = 1;
  }
  int leftup = 0; // 左上角某个位置的值
  for (int i = 1; i < n; i++) {
    for (int j = aim; j > 0; j--) {
      leftup = max;
      // if (j - arr[i] >= 0 && dp[i][j - arr[i]] != max) //之前是只要 a[i][j-cur]上有值就赋值
      if (j - arr[i] >= 0 && dp[j - arr[i]] != max) {
        leftup = dp[j - arr[i]] + 1;
      }
      dp[j] = Math.min(leftup, dp[j]);
    }
  }
  return dp[aim] != max ? dp[aim] : -1;
}