wordpress漂亮手机网站模板,wordpress 表格处理,沈阳城乡建设工程信息网,wordpress自动升级了多重背包理论
描述#xff1a;
有N种物品和一个容量为V 的背包。
第i种物品最多有Mi件可用#xff0c;每件耗费的空间是Ci #xff0c;价值是Wi 。
求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量#xff0c;且价值总和最大。 本质#xff1a;
…多重背包理论
描述
有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.hint 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 i0;inumber;i){//这个写法可以记一下scanf(%d,weighti);}for(int i0;inumber;i){scanf(%d,pricesi);}for(int i0;inumber;i){scanf(%d,limiti);}int dp[container1];memset(dp,0,sizeof(dp));for (int i0;inumber;i){for(int jcontainer;jweight[i];j--){for (int k1;klimit[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 eg100,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(numsSize0 || numsSize1) return nums[0];memset(dp,0, sizeof(dp));dp[0]nums[0];dp[1]fmax(nums[0], nums[1]);for (int i2;inumsSize;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(numsSize0 || numsSize1) return nums[0];int dp[numsSize];memset(dp, 0, sizeof(dp));dp[0]nums[0];dp[1]fmax(nums[0], nums[1]);for(int j2;jnumsSize;j){dp[j]fmax(dp[j-2]nums[j], dp[j-1]);}return dp[numsSize-1];
}int rob(int* nums, int numsSize) {if(numsSize0 || numsSize1) return nums[0];int atryrob(nums, numsSize-1);int btryrob(nums1, 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(rootNULL) {dp[0]0;dp[1]0;return dp;}int *lefttryrob(root-left);int *righttryrob(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 *atryrob(root);return fmax(a[0],a[1]);}
