文和906

题解

未归档(4) 项目笔记(5)

/ 注册

全部文章 / 题解（共2篇）

题解 | #【模板】完全背包#

这道题在弄懂01背包问题后基本没有难度。基本思路与01背包问题相同。唯一不同的是，题目中的物品可以重复加入，而01背包问题中要避免物品重复加入。在01背包问题中，避免重复添加一件物品是通过逆序遍历来实现的，而在本题中要包含重复添加一件物品的情况，只需将逆袭改为正序遍历即可。附01背包问题题解 #i...

C++ 动态规划背包问题

2021-11-01

5 637

题解 | #【模板】01背包#

经典01背包问题。解题思路比较常规。用辅助数组res存储容积为i时能装入物品的最大价值。对物品进行遍历，每次遍历中都逆序更新res，转移方程为res[j]=max(res[j-v[i]]+p[i],res[j])。最终res[v]即为要求的容积为v时所能装入物品的最大价值。这道题设置了两问，解题上有...

C++ 背包问题动态规划

2021-11-01

1 891