Java背包

问题描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

01背包

物品价值：0,3,4,5,6
物品体积：0,2,3,4,5

背包问题都是基于这张表，通过查表避免重复计算，例如斐波那契 f1+f2; f2+f3 f2用了两次。
物品编号：在第i行，我可以选择0…i的所有物品，表中值为当前状况下的最高价值

如何得到这张表？

当拿到一个背包（第一个状态），看到一个物品E（第二个状态），我们有两个选择：

• 如果背包空间不够，放不下，那么这个物品是否看到都无所谓，和第一个状态相同

 dp[i][j] = dp[i - 1][j];
1

• 如果空间足够，那我可以拿出背包的物品，腾出足够空间来装这个物品E，因为拿出物品会减少总价值，装物品会增加总价值，所以要选择最大价值的情况。

 int condition1 = dp[i - 1][j];
 int condition2 = dp[i-1][j - w[i]] + v[i];
 dp[i][j] = Math.max(condition1, condition2);
1
2
3

二维数组先行先列都可以。
完整代码

    void createTable() {
//        i 物品编号;  j 背包容量; N物品数; V 最大容量  
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < V+1; j++) {
                if (j < w[i])
                    dp[i][j] = dp[i - 1][j];
                else{
                    int condition1 = dp[i - 1][j];
                    int condition2 = dp[i-1][j - w[i]] + v[i];
                    dp[i][j] = Math.max(condition1, condition2);
                }
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

优化

空间：在状态转移时我们需要的是 dp[i - 1][j];，dp[i-1][j - w[i]]。这些都来自上一行的前半部分，所以我们可以考虑使用一维数组来记录上一行，并且从后向前遍历，这样我们所使用的都是都是上一行且没有改动的数据。
遍历：一维数组的情况下，f[j]在没有处理时，是上一行容量为j的值，处理时如果：

• j < v[i] ： f[j] = f[j]
• else： f[j] = Math.max(f[j], f[j - v[i]] + w[i]);

也就在第一种情况可以不用处理f[j]

    void createTable1() {
        int[] f = new int[V+1];
        for (int i = 0; i < N; i++) {
            for (int j = V; j >= v[i]; j--) {
                f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
            }
            System.out.println(Arrays.toString(f));
        }
    }
1
2
3
4
5
6
7
8
9

完全背包

每一个物品能取无限次

暴力

首先使用01背包方式，在要装这个物品时我们可以装入k个物品，k的上限取决于背包容量，然后在这k中情况和原状态下选择价值最高的状态

 void createTable1() {
        int[] f = new int[V + 1];
        for (int i = 0; i < N; i++) {
            for (int j = V; j >= 0; j--) {
                for (int k = 0; j >= k * v[i]; k++) {
                    f[j] = Math.max(f[j], f[j - k * v[i]] + k * w[i]);
                }
            }
            System.out.println(Arrays.toString(f));
        }
    }
1
2
3
4
5
6
7
8
9
10
11

递推

f[i,j] = max(f[i,j],f[i,j-v]+w,f[i,j-2v]+2w)
f[i,j-v] = max(f[i,j-v],f[i,j-2v]+w)
推出 f[i,j] = f[i,j-v]+w
转化为一维：

• 刚刚01背包逆序的目的是为了获取上一行的值，而这个公式需要本行左边的数据，所以从右开始遍历。

    void createTable1() {
        int[] f = new int[V + 1];
        for (int i = 0; i < N; i++) {
            for (int j = v[i]; j <= V; j++) {
                f[j] = Math.max(f[j], f[j -  v[i]] +  w[i]);
            }
            System.out.println(Arrays.toString(f));
        }
    }
1
2
3
4
5
6
7
8
9

多重背包

每个物品可以取k次
和完全背包很想，只不过完全背包的k是和容量相关，但多重因为次数随机，得不到递推关系式

二进制优化

考虑将多重背包转化为01背包，如果给我9个a物品，那可以将9个a物品看做9个价值体积相同 的不同物品(只能取一次)，这样就可以将9个物品当做01背包处理，但是这样并没有速度上的提高。
回顾这样转化的条件：

• 我可以拿任意n个物品（n
• 这这些转化后的不同物品的总和等于原先a物品的数量

还是a类物品，我如果这样分（2 * a代表这个物品的价值和体积都是a的两倍）
1 * a
2 * a
4 * a
2 * a【最后剩余9-7】
这样也可以满足上述的条件（例如1111可以表示任意小于8的数)，但不需要一个个去尝试，复杂度降为logn

这个优化，相当于每遇到一个物品，就把它拆成01背包的物品，最后用01背包的方式处理

    public void findMax() {
//            拆分二进制
        ArrayList<int[]> items = new ArrayList<>();
        for (int i = 0; i < w.length; i++) {
            int num = s[i];
            int k = 1;
            while(num >= k){
                items.add(new int[]{k * v[i], k * w[i]});
                num = num - k;
                k = k<<1;
            }
            if (num > 0)//最后有剩余
                items.add(new int[]{num * v[i], num * w[i]});
        }
//        01背包
        for (int[] item : items) {
            System.out.println(item[0]+" "+item[1]);
            for (int i = capacity; i >= item[0]; i--) {
                f[i] = Math.max(f[i], f[i - item[0]] + item[1]);
            }
            System.out.println(Arrays.toString(f));
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

混合背包

有的物品只能取一次
有的物品能取无限次
有的物品能取k次

如果一行行的遍历，在遇到 i 物品是，只需要判断是哪一种，然后按照它的种类对应处理即可

    void findMax(int[] w, int[] v, int[] s, int capacity, int[] f) {
        for (int i = 0; i < w.length; i++) {
            int flag = s[i];
            if (flag == -1) {//01
                for (int j = capacity; j >= w[i]; j--) {
                    f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
                }
            } else if (flag == 0) {//完全
                for (int j = w[i]; j < capacity + 1; j++) {
                    f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
                }
            } else {//多重
                LinkedList<int[]> items = new LinkedList<>();
                int k = 1;
                while (flag >= k) {//拆分二进制
                    items.add(new int[]{k * w[i], k * v[i]});
                    flag = flag - k;
                    k <<= 1;
                }
                if (flag > 0) {//不可拆分的部分
                    k = flag;
                    items.add(new int[]{k * w[i], k * v[i]});
                }
                for (int[] item : items) {// 将items中的元素当做01背包处理
                    for (int j = capacity; j >= item[0]; j--) {
                        f[j] = Math.max(f[j], f[j - item[0]] + item[1]);
                    }
                }
            }
            System.out.println(Arrays.toString(f));
        }
    }
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

二维背包

物品除了体积还有质量，这两个都是限制条件

f[j]在原来的基础上增加一维，01背包的基础上嵌套一层循环

 f[j][k] = Math.max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
1

很像上面的多重，完全，都是在01的基础上添加条件，你也可以在01背包的基础上修改，在处理dp[i][j]时，根据添加的条件，再加一层筛选。

  void findMax() {
        for (int i = 0; i < w.length; i++) {
            for (int j = V; j >= v[i]; j--) {
                for (int k = M; k >= m[i]; k--) {
                    f[j][k] = Math.max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
                }
            }
            System.out.println(Arrays.deepToString(f));
        }
    }
1
2
3
4
5
6
7
8
9
10

分组背包

有G个组，每个组内N个物品，但同一个组中只能,拿一件物品

转化为01，每个组看做是背包，处理时，尝试不同的物品，获得最优解。

    void findMax() {
        Scanner scanner = new Scanner(System.in);
        int G = scanner.nextInt();
        int V = scanner.nextInt();
        int[] f = new int[V + 1];
        for (int i = 0; i < G; i++) {//01
            int N = scanner.nextInt();
            int[] v = new int[N];
            int[] w = new int[N];
            for (int j = 0; j < N; j++) {
                v[j] = scanner.nextInt();
                w[j] = scanner.nextInt();
            }
            for (int j = V; j >= 0; j--) {
                for (int k = 0; k < N; k++) //在组内再进行择优
                    if(j>=v[k])
                        f[j] = Math.max(f[j], f[j - v[k]] + w[k]);

            }
        }
        System.out.println(f[V]);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

初始化问题

上面只能给出最优解，但不能保证恰好装满，如何实现这个目标呢？

   Arrays.fill(f, Integer.MIN_VALUE);
   f[0] = 0;
1
2

为什么？

  f[j] = Math.max(f[j], f[j -  v[i]] +  w[i]);
1

如果f[j]大于0，也就代表f[j - v[i]]一定来自f[0], 也就是 j = v[i]
物品总体积 = 背包容量