Backpack III

unbounded knapsack problem (UKP)

重复选择 + 最大价值

Hard

Description

Givenn_kind of items with size Aiand value Vi(each item has an infinite number available) and a backpack with size_m. What's the maximum value can you put into the backpack?

You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.

Example

Given 4 items with size[2, 3, 5, 7]and value[1, 5, 2, 4], and a backpack with size10. The maximum value is15.

Analysis

完全背包问题，DP经典

https://zhengyang2015.gitbooks.io/lintcode/backpack_iii_440.html

和II不同的是，这道题物品可以重复选择，所以内层遍历j的时候从小到大遍历，这样物品可以重复选取。比如一开始在j的时候取了i，然后随着j的增大，在j'的时候又取了i，而恰好j = j' - A[i]，在这种情况下i就被重复选取。如果从大往小遍历则所有物品只能取一次，所以II中是从大往小遍历。

因此可以重复取元素则背包容量从小到大遍历，反之从大到小遍历。

转化为多重背包问题

将其视为多重背包变形，每种物品取的上限是m / A[i]。

可以无限使用物品, 就失去了last i, last unique item的意义: 因为可以重复使用. 所以可以转换一个角度:
- i. 用 i 种物品, 拼出j大小, 并且满足题目条件(max value). 这里因为item i可以无限次使用, 所以考虑使用了多少次K.
- ii. k虽然可以无限, 但是也被 k * A[i]所限制: 最大不能超过背包大小.
dp[i][j]: 前i种物品, fill weight j 的背包, 最大价值是多少.
dp[i][j] = max {dp[i - 1][j - k*A[i-1]] + k*V[i-1]}, k >= 0, k <= j / A[i-1]
Time: O(nmk)
如果k = 0 或者 1, 其实就是 Backpack II: 0-1背包，拿或者不拿

2D - DP示意图：

2D - DP 代码实现：

/*
Thoughts:
dp[i][w]: first i types of items to fill weight w, find the max value.
1st loop: which type of item to pick from A
2nd loop: weight from 0 ~ m
3rd loop: # times when A[i] is used.
Goal: dp[n][m]
Condition1: didn't pick A[i - 1], dp[i][j] = dp[i - 1][j];
Condition2: pickced A[i - 1], dp[i][j] = dp[i - 1][j - k * A[i - 1]] + k * V[i - 1];
O(nmk)
*/

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
            return 0;
        }
        int n = A.length;
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = 0; // 0 items to fill 0 weight, value = 0

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k * A[i - 1] <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
                }
            }
        }

        return dp[n][m];
    }
}

Minor Modified

public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
            return 0;
        }
        int n = A.length;
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = 0; // 0 items to fill 0 weight, value = 0

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k * A[i - 1] <= j; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
                }
            }
        }

        return dp[n][m];
    }
}

时间复杂度优化

优化时间复杂度, 通过画图（见以上示意图）发现:
- 所计算的 (dp[i - 1][j - k*A[i - 1]] + k * V[i - 1]) ，其实跟同一行的 dp[i][j-A[i-1]] 那个格子相比, 就多出了 V[i-1]
- 所以没必要每次都 loop over k times
简化: dp[i][j] 其中一个可能就是: dp[i][j - A[i - 1]] + V[i - 1]
Time: O(mn)
Space: O(mn)

/**
Optimization1: 
- 优化时间复杂度, 画图发现:
- 所计算的 (dp[i - 1][j - k*A[i - 1]] + k * V[i - 1]) 
- 其实跟同一行的 dp[i][j-A[i-1]] 那个格子, 就多出了 V[i-1]
- 所以没必要每次都 loop over k times
- 简化: dp[i][j] 其中一个可能就是: dp[i][j - A[i - 1]] + V[i - 1]

*/
public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
            return 0;
        }
        int n = A.length;
        int[][] dp = new int[n + 1][m + 1];
        dp[0][0] = 0; // 0 items to fill 0 weight, value = 0

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= A[i - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]);
                }
            }
        }
        return dp[n][m];
    }
}

空间复杂度优化

空间优化到1维数组

根据上一个优化的情况, 画出 2 rows 网格
- 发现 dp[i][j] 取决于: 1. dp[i - 1][j], 2. dp[i][j - A[i - 1]]
- 其中: dp[i - 1][j] 是上一轮 (i-1) 的结算结果, 一定是已经算好, ready to be used 的
- 然而, 当我们 i++, j++ 之后, 在之前 row = i - 1, col < j 的格子, 全部不需要.
降维简化: 只需要留着 weigth，也就是j这个 dimension, 而 i 这个dimension 可以省略:
- (i - 1)th row 不过是需要用到之前算出的旧value: 每一轮, j = [0 ~ m], 那么dp[j]本身就有记录旧值的功能.
- 变成1个一维数组
降维优化的重点: 看双行的左右计算方向
Time: O(mn).
Space: O(m)

/**
Optimization2: 
- 根据上一个优化的情况, 画出 2 rows 网格
- 发现 dp[i][j] 取决于: 1. dp[i - 1][j], 2. dp[i][j - A[i - 1]]
- 其中: dp[i - 1][j] 是上一轮 (i-1) 的结算结果, 一定是已经算好, ready to be used 的
- 然而, 当我们 i++,j++ 之后, 在之前 row = i - 1, col < j的格子, 全部不需要.
- 降维简化: 只需要留着 weigth 这个 dimension, 而i这个dimension 可以省略: 
- (i - 1) row 不过是需要用到之前算出的旧value: 每一轮, j = [0 ~ m], 那么dp[j]本身就有记录旧值的功能.
*/
public class Solution {
    public int backPackIII(int[] A, int[] V, int m) {
        if (A == null || A.length == 0 || V == null || V.length == 0 || m <= 0) {
            return 0;
        }
        int n = A.length;
        int[] dp = new int[m + 1]; // DP on weight
        dp[0] = 0; // 0 items to fill 0 weight, value = 0

        for (int i = 1; i <= n; i++) {
            for (int j = A[i - 1]; j <= m && j >= A[i - 1]; j++) {
                dp[j] = Math.max(dp[j], dp[j - A[i - 1]] + V[i - 1]);
            }
        }
        return dp[m];
    }
}

关于最优化算法的细节：

时间复杂度为 O(mn)，空间复杂度为 O(m)

九章：

优化的方法十分简单，我们只需要将 j 的循环由逆向转变为正向即可。想一想，为什么？由于同一种物品的个数无限，所以我们可以在任意容量 j 的背包尝试装入当前物品，j 从小向大枚举可以保证所有包含第 i 种物品，体积不超过 j - A[i] 的状态被枚举到。从而得到时间复杂度为 O(mn)，空间复杂度为 O(m) 的优秀算法。

https://blog.csdn.net/roufoo/article/details/83117144

j从大到小取，可以保证dp[j]里面的值是每个item只取了一个的时候的最优值。所以01背包和多重背包的k循环只能从大到小取，而完全背包的k循环从大到小和从小到大都可以。这是01背包/多重背包和完全背包的一个重要区别！

正序和逆序的区别就是，对于正序，j以前的状态是当前行的状态；对于逆序，j以前的状态是上一个行的状态。

Reference

PreviousBackpack II NextBackpack IV

Last updated 4 years ago