算法&OJ--其他--背包问题

发表于 | 分类于 | 阅读次数:
  • 总结两类
    • 01背包问题
    • 部分背包问题

01背包问题

往背包中装物品。物品有重量和价值属性。每个物品只有一件且不能分割，在不超过背包容量的同时，如何选取物品，使得背包所装的价值最大（背包可以装不满）

  • 经典的DP动态规划问题
    • 具有最优子结构(在此略去证明过程)

  • 递归求解

    • 每个物品都可以选择放入或不放入，n个物品就需要做n次选择
    • 设f[i][w]表示前i件物品恰放入一个容量为w的背包可获得的最大价值
      • 如果放入第i件物品，则f[i][w] = f[i-1][w-w[i]] + v[i]
      • 如果不放入第i件，则f[i][w] = f[i-1][w]
      • 显然有f[i][w] = max(f[i-1][w-w[i]]+v[i], f[i-1][w])
    • 结合以下实例来理解：往容量的50的包里装(W,A)分别为以下的物品(10,60)、(20,100)、(30,120)
      image

  • 优化空间

    • 采用一维数组来记录每次的判断结果
    • 最终能完全利用该背包的必然是最大价值(即数组最后一个元素)
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
43
44
45
46
47
48
49
50
51
52
53
54
55
// LintCode-125.背包问题 二
/**
 * 问题描述：给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？
 * @param m: An integer m denotes the size of a backpack
 * @param A: Given n items with size A[i]
 * @param V: Given n items with value V[i]
 * @return: The maximum value
 */
public int backPackII(int m, int[] A, int[] V) {
    // 边界情况
    if(A==null || V==null || A.length!=V.length || A.length==0 || m<=0) {
        return -1;
    }
    int[] dp = new int[m+1];
    int max = 0;
    for(int i=0; i<A.length; i++) {
        for(int j=m; j>=A[i]; j--) {
            if(dp[j-A[i]]+V[i] > dp[j]) {
                dp[j] = dp[j-A[i]]+V[i];
            }
            if(dp[j] > max) {
                max = dp[j];
            }
        }
    }
    return max;
}


// 变式
// LintCode-92.背包问题
/**
 * 问题描述：在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]。(不可切割物品)
 * @param m: An integer m denotes the size of a backpack
 * @param A: Given n items with size A[i]
 * @return: The maximum size
 */
public int backPack(int m, int[] A) {
    if(A==null || A.length==0 || m<=0) return -1;
    int n = A.length;
    int[] dp = new int[m+1];
    int max = -1;
    
    for(int i=0 ;i<n; i++) {
        for(int j=m; j>=A[i]; j--) {
            if(dp[j-A[i]] + A[i] > dp[j]) {
                dp[j] = dp[j-A[i]] + A[i];
                if(dp[j] > max) {
                    max = dp[j];
                }
            }
        }
    }
    return max;
}

部分背包问题

  • 问题描述
  • 思路
    • 计算出平均价值重量value/weight
    • 按照value/weight从高到低填充背包
    • 最后剩下的装不下的空间，按照该均值乘以剩余容量
物品 重量 价值 单位重量的价值量
A 10 60 6
B 20 100 5
C 30 120 4
  • 例如有如下问题
    • 背包容量是50，求背包可以装三种物品的最大价值(物品可以被拆分)
    • 由于可以拆分，考虑的是单位重量的价值量
    • 可以轻易求得最优价值是：60+100+4*(50-30)=240

完全背包问题

  • 待整理ing

参考资料