光与影的个人博客

NEUCoder

0%

lc2212.射箭比赛中的最大比赛

发表于 更新于 分类于 ，

2212. 射箭比赛中的最大得分

打周赛遇到的一道非常典型的0-1背包问题，但是因为太久没写过背包问题，写了40分钟才写出来，再温习一遍。

什么是0-1背包？

一共有N个物品，每个物品有对应的重量weight[i] 和价值value[i]，给定一个固定容量W的背包，问能够放入背包的最大价值是多少？非常经典又相对简单的动态规划问题，关键还是在于定义状态以及状态转移公式。

贪心的角度出发，假设我选取某个物品后，新的贪心目标变为 在剩余物品和空间的条件下，选取最大价值的物品，因此父问题到子问题的转化可以定义为：（按照从左到右一个一个选的思路）

  • 父问题：是否选取第i个物品，使得总价值最大
  • 子问题：父问题 选 / 不选 第i个物品， 背包剩余 W-w[i] / W空间，如何在前i-1物品中合适选取使得子问题价值最大

dp状态可以定义为：

1
dp[i][j]: 将前i个物品装到容量为j的背包中的最大价值

状态转移公式为:

  1. 选取第i个物品

    1
    dp[i][j] = v[i] + dp[i][j - w[i]]

  2. 不选第i个物品（或者当前容量无法选取第i个物品）

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

  • 最后公式为

    1
    dp[i][j] = max(v[i] + dp[i][j - w[i]], dp[i - 1][j])

复杂度分析:

  1. 时间复杂度：自下而上（前i物品）计算状态，每个物品需要遍历所有的背包容量，时间复杂度为 O(NW)，即物品数量乘以背包容量
  2. 空间复杂度： 类似时间复杂度分析，存储所有状态需要 O(NW)，若使用存储压缩，只需要一个长度等于背包容量的数组，但是若要存储解，则无法压缩，空间复杂度为 O(NW) 或者 O(W)

模板伪代码:

1
2
3
4
5
6
# dp数组长度为w+1,多一个为了减少越界判断
dp[0,1,2,3....,w] = 0
for i in [0,1,2,3,4,5,6,7,8,9....n]:
	for j in [w,w - 1,....1]:
		# j > w[i],反向遍历避免状态丢失（因为只用了一维数组存储状态）
		dp[j] = max(dp[j], dp[j−w[i]]+v[i])

射箭问题

非常明显的0-1背包问题，箭支数量为”背包容量”，占领每个区域所需要的箭为”物品重量“，每个区域的分数为”价值”，转化为0-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
class Solution {
    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        // dp状态数组
        int[] dpArray = new int[numArrows + 1];
        int[][] solution = new int[aliceArrows.length][numArrows + 1];
        for(int i = 0;i < aliceArrows.length;i++){
            for(int j = numArrows;j > 0;j--){
                if(j > aliceArrows[i] && i + dpArray[j - aliceArrows[i] - 1] > dpArray[j]){
                    dpArray[j] = i + dpArray[j - aliceArrows[i] - 1];
                    solution[i][j] = 1;
                }
            }
        }

        //生成结果数组(比较重要的一部分代码)
        int[] result = new int[aliceArrows.length];
        int curArrows = numArrows;
        for(int i = aliceArrows.length - 1;i > 0;i--){
            if(solution[i][curArrows] == 1){
                result[i] = aliceArrows[i] + 1;
                curArrows -= aliceArrows[i] + 1;
            }
        }
        result[0] = curArrows;
        return result;
    }
}