网站开发计划书模板,网站备案换接入商,2013我国中小企业接入互联网和网站建设情况,网站后台管理系统页面文章目录 1、动规思路简介2、完全背包【模板】3、零钱兑换4、零钱兑换Ⅱ5、完全平方数 背包问题需要读者先明白动态规划是什么#xff0c;理解动规的思路#xff0c;并不能给刚接触动规的人学习。所以最好是看了之前的动规博客#xff0c;以及01背包博客#xff0c;才能看完… 文章目录 1、动规思路简介2、完全背包【模板】3、零钱兑换4、零钱兑换Ⅱ5、完全平方数 背包问题需要读者先明白动态规划是什么理解动规的思路并不能给刚接触动规的人学习。所以最好是看了之前的动规博客以及01背包博客才能看完全背包博客或者你本人就已经懂得动规了。 1、动规思路简介
动规的思路有五个步骤且最好画图来理解细节不要怕麻烦。当你开始画图仔细阅读题时学习中的沉浸感就体验到了。 状态表示 状态转移方程 初始化 填表顺序 返回值 动规一般会先创建一个数组名字为dp这个数组也叫dp表。通过一些操作把dp表填满其中一个值就是答案。dp数组的每一个元素都表明一种状态我们的第一步就是先确定状态。
状态的确定可能通过题目要求来得知可能通过经验 题目要求来得知可能在分析过程中发现的重复子问题来确定状态。还有别的方法来确定状态但都大同小异明白了动规这些思路也会随之产生。状态的确定就是打算让dp[i]表示什么这是最重要的一步。状态表示通常用某个位置为结尾或者起点来确定。
状态转移方程就是dp[i]等于什么状态转移方程就是什么。像斐波那契数列dp[i] dp[i - 1] dp[i - 2]。这是最难的一步。一开始可能状态表示不正确但不要紧大胆制定状态如果没法推出转移方程没法得到结果那这个状态表示就是错误的。所以状态表示和状态转移方程是相辅相成的可以帮你检查自己的思路。
要确定方程就从最近的一步来划分问题。
初始化就是要填表保证其不越界。像第一段所说动规就是要填表。比如斐波那契数列如果要填dp[1]那么我们可能需要dp[0]和dp[-1]这就出现越界了所以为了防止越界一开始就固定好前两个值那么第三个值就是前两个值之和也不会出现越界。初始化的方式不止这一点有些问题假使一个位置是由前面2个位置得到的我们初始化最一开始两个位置然后写代码会发现不够高效这时候就需要设置一个虚拟节点一维数组的话就是在数组0位置处左边再填一个位置整个dp数组的元素个数也1让原先的dp[0]变为现在的dp[1]二维数组则是要填一列和一行设置好这一行一列的所有值原先数组的第一列第一行就可以通过新填的来初始化这个初始化方法在下面的题解中慢慢领会。
第二种初始化方法的注意事项就是如何初始化虚拟节点的数值来保证填表的结果是正确的以及新表和旧表的映射关系的维护也就是下标的变化。
填表顺序。填当前状态的时候所需要的状态应当已经计算过了。还是斐波那契数列填dp[4]的时候dp[3]和dp[2]应当都已经计算好了那么dp[4]也就出来了此时的顺序就是从左到右。还有别的顺序要依据前面的分析来决定。
返回值要看题目要求。 背包问题有很多种分类此篇是关于完全背包问题的优化方法写在模板题中此后都直接写在代码上。 2、完全背包【模板】
DP42 【模板】完全背包 和01背包不同的是完全背包一个数可以选择多次。dp[i][j]表示从前i个物品中选总体积不超过j所有选法中最大的价值。
最后一个位置i如果不选那就看dp[i - 1][j]如果选1个那就看dp[i - 1][j - v[i]] w[i]如果选2个那就看dp[i - 1][j - 2v[i]] 2w[i]依次类推这里只有j和后面的w变了那么再按照这个式子写出dp[i][j - v[i]]的值最后通过数学计算能得到dp[i][j] max(dp[i - 1][j], dp[i][j - v[i]] w[i])。
初始化时新增的一行一列全部为0。从上到下从左到右填写返回值是dp[n][V]。
接着第二问再上面基础上做调整。 dp[i][j]表示体积必须等于j。按照之前的思路dp[i][j] -1来表示这个情况不存在做不到要求。初始化时dp[0][0] 0第一行其余位置都是-1第一列还是0。
#include iostream
#include cstring
using namespace std;const int N 1010;int n, V, v[N], w[N];
int dp[N][N];int main()
{cin n V;for(int i 1; i n; i){cin v[i] w[i];}for(int i 1; i n; i){for(int j 0; j V; j){dp[i][j] dp[i - 1][j];if(j v[i]) dp[i][j] max(dp[i][j], dp[i][j - v[i]] w[i]);}}cout dp[n][V] endl;memset(dp, 0, sizeof(dp));for(int j 1; j V; j) dp[0][j] -1;for(int i 1; i n; i){for(int j 0; j V; j){dp[i][j] dp[i - 1][j];if(j v[i] dp[i][j - v[i]] ! -1)dp[i][j] max(dp[i][j], dp[i][j - v[i]] w[i]);}}cout (dp[n][V] -1 ? 0 : dp[n][V]) endl;return 0;
}利用滚动数组做优化。和01背包不一样它不需要从右到左来循环它的一个位置需要同行的左边的一个位置和上方一个位置同行这个位置得是更新后的。
#include iostream
#include cstring
using namespace std;const int N 1010;int n, V, v[N], w[N];
int dp[N];int main()
{cin n V;for(int i 1; i n; i){cin v[i] w[i];}for(int i 1; i n; i){for(int j v[i]; j V; j){dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout dp[V] endl;memset(dp, 0, sizeof(dp));for(int j 1; j V; j) dp[j] -1;for(int i 1; i n; i){for(int j v[i]; j V; j){if(dp[j - v[i]] ! -1)dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout (dp[V] -1 ? 0 : dp[V]) endl;return 0;
}还有一个优化 memset(dp, 0, sizeof(dp));for(int j 1; j V; j) dp[j] -1;for(int i 1; i n; i){for(int j v[i]; j V; j){if(dp[j - v[i]] ! -1)dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout (dp[V] -1 ? 0 : dp[V]) endl;这里有一个if判断是为了能让这个dp值可用再去让他w[i]和dp[j]比较我们可以让那个dp表中的每一个值足够小这样即使dp[j - v[i]]参与了比较也不会用它。 memset(dp, 0, sizeof(dp));for(int j 1; j V; j) dp[j] -0x3f3f3f3f;//INT_MIN的一半也足够小。for(int i 1; i n; i){for(int j v[i]; j V; j){dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout (dp[V] 0 ? 0 : dp[V]) endl;3、零钱兑换
322. 零钱兑换 dp[i][j]表示从前i个硬币中选总金额正好等于j所有的选法中最少的硬币个数j就是amount。
最后一个位置i不选的话就看dp[i - 1][j]。如果选i选1个那么这个硬币价值就是coins[i]那为了能正好达到j而不超过那就得看dp[i - 1][j - coins[i]]然后1因为存的是个数如果选2个那么就是dp[i - 1][j - 2coins[i]] 2根据之前的数学计算选i的情况就是dp[i][j - coins[i]] 1然后和dp[i - 1][j]取小就行。
初始化时多加一行一列dp[0][0]是0第一行其它位置是无效的因为没有硬币的话就不可能凑成金额按照之前的优化本来设置成-1然后判断这里就初始化成足够大的数字就行因为这道题就min初始化成0x3f3f3f3f。
返回最后一个位置的值但有可能到最后也凑不成所以最后要判断一下。以及滚动数组优化。 int coinChange(vectorint coins, int amount) {const int INF 0x3f3f3f3f;int n coins.size();vectorint dp(amount 1, INF);dp[0] 0;for(int i 1; i n; i){for(int j coins[i - 1]; j amount; j){dp[j] min(dp[j], dp[j - coins[i - 1]] 1);}}return dp[amount] INF ? -1 : dp[amount];}4、零钱兑换Ⅱ
518. 零钱兑换 II 看了上一个题的思路这题很快就出来答案了。
上一个题代码 int coinChange(vectorint coins, int amount) {const int INF 0x3f3f3f3f;int n coins.size();vectorint dp(amount 1, INF);dp[0] 0;for(int i 1; i n; i){for(int j coins[i - 1]; j amount; j){dp[j] min(dp[j], dp[j - coins[i - 1]] 1);}}return dp[amount] INF ? -1 : dp[amount];}现在要求组合数所以选i的情况中就不需要1了。不用求min而是所有可能的数值加起来按照优化后的代码dp[j] dp[j] dp[j - coins[i]]返回时不需要判断直接返回最后一个位置的值即可。 int change(int amount, vectorint coins) {int n coins.size();vectorint dp(amount 1);dp[0] 1;for(int i 1; i n; i){for(int j coins[i - 1]; j amount; j){dp[j] dp[j - coins[i - 1]];}}return dp[amount];}5、完全平方数
279. 完全平方数 也是一个完全背包问题dp[i][j]表示从前i个完全平方数中挑选总和正好等于j所有选法中最小的数量。
从1到i方的区间来分析不选i方那就看dp[i - 1][j]选一个i方那就看dp[i - 1][j - i^2] 1选两个i方和之前的一样最后就是dp[i][j - i^2] 1然后两个数取min。
初始化dp[0][0]是0第一行其余位置都是不存在的所以也弄成特殊值0x3f3f3f3f第一列不用管默认为0就行。
返回值是dp[根号n][n]。 int numSquares(int n) {int m sqrt(n);vectorint dp(n 1, 0x3f3f3f3f);dp[0] 0;for(int i 1; i m; i){for(int j i * i; j n; j){dp[j] min(dp[j], dp[j - i * i] 1);}}return dp[n];}结束。
