VIVO笔试题——背包问题

背景：VIVO提前批笔试题遇到了01背包，就记得动态规划动态规划，记得表格法，突然失忆怎么写。

来自背包九讲

01背包

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的容量是 Ci，得到的

价值是 Wi。求解将哪些物品装入背包（每个物品只可放一件物品）可使价值总和最大（最优化问题）?

思路

自顶而下的方式去思考问题，设f（i，v）为选取前 i 件物品装入容量为 v 的背包中的物品最大值；那么f（i，v）等于不选 i 物品的 f 和选 i 物品(判断容量范围)的 f 的最大值。

即：

f(i,v) = max{f(i-1,v),f(i-1,v-Ci)+Wi}

思考问题用自顶而下的方式，但是编码的话，若是自顶而下必然会出现“子问题的重叠”而导致的时间复杂度的提高。

那么就采用，自下而上的方式去编码，既然

f(i,v) = max{f(i-1,v),f(i-1,v-Ci)+Wi}

，那么就从f(0,v)、f(1,v)开始循环去计算，避免了重复的子问题的计算。

编码

（1）初始化耗费容量和总容量(递增)的二维dp数组，第0行第0列初始化为0；

（2）编写状态转移方程，注意每一列是

从 Ci 到 V

或者

从1到V + 容量判断

。

public static int dpCore1(int V, int[] cost, int[] value) {
        int N = cost.length;
        // 初始化数组表格
        int[][] dp = new int[N + 1][V + 1];
        // 前0个物品,全是0
        for (int i = 0; i < N + 1; i++) {
            dp[i][0] = 0;
        }
        // 没有容量,全是0
        for (int i = 0; i < V + 1; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < N + 1; i++) {
            for (int j = cost[i-1]; j < V + 1; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cost[i - 1]] + value[i - 1]);
            }
        }
        return dp[N][V];
    }
           

空间优化

思考，

f(i,v) = max{f(i-1,v),f(i-1,v-Ci)+Wi}

->

f(v) = max{f(v),f(v-Ci)+Wi}

用一个f[0…v]保存当前价格最大值，那么将第二个循环从V到Ci倒着来遍历，这样就保证了在推f[v]的时候用的是上一轮计算的结果，即f[v-ci]保存的状态是上一轮计算的f(i-1,v-ci)（因为倒着来，较小的值还没更新）

编码

public static int dpCore2(int V, int[] cost, int[] value) {
        int N = cost.length;
        // 初始化dp一维数组
        int[] dp = new int[V + 1];
        for (int i = 1; i < N + 1; i++) {
            for (int j = V; j >= cost[i - 1]; j--) {
            	// 注意此处是倒着来的,j - cost[i - 1]此时是比j小的数字,由于是倒着来的,故还没更新,保存的内容是上一轮的
                dp[j] = Math.max(dp[j], dp[j - cost[i - 1]] + value[i - 1]);
            }
        }
        return dp[V];
    }
           

初始化问题

思想来自背包九讲：若要求背包必须装满，那么初始化dp数组时，除了dp[0]为0外其他的都为

负无穷

；若不要求装满，而是价值尽量大，那么dp全部初始化为

。含义就是：若果必须装满，那么只有在容量为0且什么都不装的情况下才能满足要求，容量＞0没有合法解；若不要求装满，那在各个容量情况下都可以不放而为0。

完全背包问题

完全背包就是物品不止一个，可以拿多次。

题目：有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 Ci，价值是 Wi。求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

思路1

类似01背包的思想，只是每一步max中多个而不是2个的对比状态，其转移方程如下：

f(i,v) = max{f(i-1,v-k*Ci)+k*Wi | 0≤k*Ci≤v}

该方程的时间复杂度为

O(NV*∑(v/ci))

，其中

∑(v/ci)

是求解每一步

f(i,v)

所需要的时间复杂度。

优化

首先将大于 V 的物品去掉，在将费用相同价值最高的选出来，再将

Ci≤Cj && Wi≥Wj

的 j 物品直接去掉，在用上述方法进行计算。

思路2

转换成01背包来求解，在给定 V 的条件下，将每一个物品拆分成

[V/Ci]

个物品，且拆分出来的物品的价值W为

k*Wi

，求解这个新的01背包问题。

更高效的转换方法：把第 i 件物品拆分成费用为Ci2k，价值为Wi2k的若干物品，其中

k

取遍满足Ci2k的非负整数。思想在于，任何一个数字都可以用二进制数表示，即多个2k才表示。这样每件物品拆分成O(log[V/Ci])件物品。

正统思路3

将01背包优化后的流程中的倒序遍历改成正序遍历。

for(int j = Ci ; i < V+1 ; j++)

之前倒序是为了f[v]是上次i-1时保存的值，而正序是为了选过之后还可以选（小的已经选过，再次比较），选其中的最大值。

多重背包问题

不是无限可拿，而是最多Mi件可用，耗费Ci、价值Wi。

思路1

还是用类似于01背包的思路，转移方程如下：

f(i,v) = max{f(i-1,v-k*Ci)+k*Wi | 0≤k*Ci≤v,0≤k≤Mi}

，时间复杂度

O(V*∑Mi*∑(v/ci))

。

思路2

还是拆分的思想，每件物品的花费和价值分别乘系数就是拆分后物品的属性，对于给的Mi，可以拆分成1,2,22,23,Mi-2k+1的系数，且k是满足Mi-2k+1>0的最大整数。若Mi=13，则可以分系数为1,2,4,6的4件物品。