代码随想录算法训练营day39||动态规划07：多重背包+打家劫舍

多重背包理论

描述：

有N种物品和一个容量为V 的背包。

第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。

求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

本质：

多重背包和01背包是非常像的，为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

——在01背包里面在加一个for循环遍历一个每种商品的数量。

56. 携带矿石资源（第八期模拟笔试）

题目描述

你是一名宇航员，即将前往一个遥远的行星。在这个行星上，有许多不同类型的矿石资源，每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球，但你的宇航舱有一定的容量限制。

给定一个宇航舱，最大容量为 C。现在有 N 种不同类型的矿石，每种矿石有一个重量 w[i]，一个价值 v[i]，以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下，最大化你所能获取的总价值。

分析：

先遍历物品，再遍历背包容量，最后遍历物品的个数

——背包遍历：0-1背包+滚动数组，需要逆序遍历；背包容量至少要能装下一个物品，遍历到weight【i】为止

——可放物品个数的遍历：

为什么不放在第二层遍历：会有大量重复，放1、2物品，和放2、3物品是一样的

考虑当前背包是放k个i物品，能装的最大价值是多少？

先考虑k的取值范围：装0个 dp【j】不变，可以不考虑；k要小于物品容量的上

限，同时j要能方向k个物品

注意递推公式：考虑加上k个物品之后的情况！补上k*value

for(int i = 0; i < n; i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量// 以上为01背包，然后加一个遍历个数for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);}}}

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h>
#include <string.h>int max(int x, int y){return x > y ? x : y;
}int main(){int container,number;scanf("%d%d",&container,&number);int weight[number],prices[number],limit[number];for(int i=0;i<number;i++){//这个写法可以记一下scanf("%d",weight+i);}for(int i=0;i<number;i++){scanf("%d",prices+i);}for(int i=0;i<number;i++){scanf("%d",limit+i);}int dp[container+1];memset(dp,0,sizeof(dp));for (int i=0;i<number;i++){for(int j=container;j>=weight[i];j--){for (int k=1;k<=limit[i] && j-k*weight[i]>=0 ;k++){dp[j]=max(dp[j],dp[j-k*weight[i]]+k*prices[i]);}}}printf("%d\n",dp[container]);return 0;
}

总结篇

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

动态规划：416.分割等和子集(opens new window)
动态规划：1049.最后一块石头的重量 II(opens new window)

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

动态规划：494.目标和(opens new window)
动态规划：518. 零钱兑换 II(opens new window)
动态规划：377.组合总和Ⅳ(opens new window)
动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

动态规划：474.一和零(opens new window)

问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

动态规划：322.零钱兑换(opens new window)
动态规划：279.完全平方数

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：[2,7,9,3,1]
输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析：

实际上j间房屋偷或者不偷有三种情况：

偷了没偷 j：偷j，是在j-2的基础上+j

没偷偷了 j：不能偷j，是和j-1是一样的

没偷没偷 j：如果要偷，同1；如果不偷同2 eg：100,1,1,100

所以本质上是讨论j偷还是不偷的问题，不要去讨论前面各个的状态

确定dp数组（dp table）以及下标的含义

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）

然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

dp数组如何初始化

从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]

从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);

确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

int rob(int* nums, int numsSize) {int dp[numsSize];//到第i栋房子，最多能偷的钱if(numsSize==0 || numsSize==1) return nums[0];memset(dp,0, sizeof(dp));dp[0]=nums[0];dp[1]=fmax(nums[0], nums[1]);for (int i=2;i<numsSize;i++){dp[i] = fmax(dp[i - 2] + nums[i], dp[i - 1]);}return dp[numsSize-1];
}

213.打家劫舍II

力扣题目链接(opens new window)

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

分析：

分成两种情况来解决环的问题！

1、包括环的头结点，不包括尾节点

2、不包括头结点，包括尾节点

再按照打家劫舍1的方法，取两种情况的最大值

即为所求结果

**注意：动态规划是考虑下标i及下标i 之前的元素，是否能达到某个条件，并不是说一定要选取这个元素的！

**环形问题可以考虑展开

int tryrob(int*nums,int numsSize){if(numsSize==0 || numsSize==1) return nums[0];int dp[numsSize];memset(dp, 0, sizeof(dp));dp[0]=nums[0];dp[1]=fmax(nums[0], nums[1]);for(int j=2;j<numsSize;j++){dp[j]=fmax(dp[j-2]+nums[j], dp[j-1]);}return dp[numsSize-1];
}int rob(int* nums, int numsSize) {if(numsSize==0 || numsSize==1) return nums[0];int a=tryrob(nums, numsSize-1);int b=tryrob(nums+1, numsSize -1);return fmax(a,b);}

337.打家劫舍 III

力扣题目链接(opens new window)

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

分析：

暴力递归

对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。

本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。——即孩子取值决定了，才能决定父亲的情况

与198.打家劫舍，213.打家劫舍II一样，关键是要讨论当前节点抢还是不抢。

如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子

动态规划

动态规划其实就是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱。

这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。

确定递归函数的参数和返回值

这里我们要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。

长度为2的数组怎么标记树中每个节点的状态：在递归的过程中，系统栈会保存每一层递归的参数。

确定终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

这也相当于dp数组的初始化

确定遍历顺序

首先明确的是使用后序遍历。因为要通过递归函数的返回值来做下一步计算。

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0]; （如果对下标含义不理解就再回顾一下dp数组的含义）

如果不偷当前节点，那么左右孩子就可以偷

至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);

最后当前节点的状态就是{val2, val1}; 即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

举例推导dp数组

以示例1为例，dp数组状态如下：（注意用后序遍历的方式推导）

最后头结点就是取下标0 和下标1的最大值就是偷得的最大金钱。

int* tryrob(struct TreeNode* root){int* dp=(int*)malloc(sizeof(int)*2);//dp表示在某一个结点往下，0是不抢该结点的最大，1是抢该节点的最大if(root==NULL) {dp[0]=0;dp[1]=0;return dp;}int *left=tryrob(root->left);int *right=tryrob(root->right);//不抢dp的话，也就是dp0，可以抢两个孩子dp[0]=fmax(left[0],left[1])+fmax(right[0],right[1]);//抢dp的话，dp1，两个孩子都不能抢dp[1]=left[0]+right[0]+root->val;return dp;
}int rob(struct TreeNode* root) {int *a=tryrob(root);return fmax(a[0],a[1]);}