常见网站建设公司术语,网站做会员用什么源码,建设企业银行网站,做正规小说网站有哪些DP初步#xff1a;状态转移与递推
最少硬币问题
有多个不同面值的硬币(任意面值)数量不限输入金额S#xff0c;输出最少硬币组合。 回顾用贪心求解硬币问题 硬币面值1、2、5。支付13元#xff0c;要求硬币数量最少 贪心: (1)5元硬币#xff0c;2个 (2)2元硬币#xff0c…DP初步状态转移与递推
最少硬币问题
有多个不同面值的硬币(任意面值)数量不限输入金额S输出最少硬币组合。 回顾用贪心求解硬币问题 硬币面值1、2、5。支付13元要求硬币数量最少 贪心: (1)5元硬币2个 (2)2元硬币1个 (3)1元硬币1个 硬币面值1、2、4、5、6.支付9元。 贪心: (1)6元硬币1个 (2)2元硬币1个 (3)1元硬币1个 错误! 答案是:5元硬币4元硬币2个
硬币问题的正解是动态规划
type [1,5,10,25,50] 5种面值 定义数组Min[]记录最少硬币数量 对输入的某个金额iMin[i]是最少的硬币数量 第一步只考虑1元面值的硬币 金额i 012345
硬币数量Min[]01234i1元时等价于i i - 1 0 元需要的硬币数量加上1个1元硬币i2元时等价于i i - 1 1 元需要的硬币数量加上1个1元硬币… 在1元硬币的计算结果基础上再考虑加上5元硬币的情况从i5开始就行了 i5元时等价于
i i - 5 0元需要的硬币数量加上1个5元硬币Min[5] 1原来的Min[5] 5 取1和2的最小值所以Min[5] 1 i 6元时等价于i i - 5 1元需要的硬币数量加上1个5元硬币Min[6] 2原来的Min[6] 6 取1和2的最小值所以Min[6] 2 Min[6] Min[5] 1 递推关系 Min[i] min (Min[i], Min[i - 5] 1) 继续处理其它面值硬币
#include iostream
#include vector
#include limits.h
using namespace std;void solve(int s)
{int cnt 5; //5种硬币vectorint type {1,5,10,25,50}; //5种面值vectorint Min(s1, INT_MAX); //初始化为无穷大Min[0] 0;for (int j 0; j cnt; j ) //5种硬币{Min[i] min (Min[i], Min[i - type[j]] 1);}cout Min[s] endl;
}int main()
{int s;cin s;solve(s);return 0;
}DP的两个特征
重叠子问题 在递归算法中尤其是在解决最优化问题时经常会遇到这样的情况在求解大问题的过程中我们需要多次求解规模更小、结构相同的问题。这些小问题被称为子问题。如果这些子问题在大问题求解过程中被重复计算多次这将导致算法效率低下因为大量时间被重复的子问题求解所占据。动态规划通过存储子问题的解(通常在二维数组中称为DP表)确保每个子问题只计算一次从而避免了重复计算。当需要某个子问题的解时直接从DP表中查找如果该子问题尚未解决则先解决它然后存储其解。最优子结构 这是动态规划能够成功解决许多问题的另一个关键特性。最优子结构是指一个问题的最优解包含其子问题的最优解。换句话说如果我们能找到所有子问题的最优解那么我们可以通过这些子问题的最优解来构建原问题的最优解。动态规划利用这个性质通过自底向上的方式(即先解决最基础的子问题然后逐步解决更大规模的子问题)来构建问题的最优解。
DP记忆化
如果各个子问题不是独立的如果能够保存已经解决的子问题的答案在需要的时候再找出已求得的答案可以避免大量的重复计算。 基本思路用一个表记录所有已解决的子问题的答案不管该问题以后是否被用到只要它被计算过就将其结果填入表中。 记忆化 解题步骤
拆分问题定义状态(并找出初状态)状态转移方程 一般的模型方法递归搜索法记忆化搜索(记忆化暴力)递推式法
最经典的DP问题0/1背包
给定n种物品和一个背包物品i的重量是 w i w_{i} wi其价值为 v i v_{i} vi背包的容量为C. 背包问题:选择装入背包的物品使得装入背包中物品的总价值最大 如果在选择装入背包的物品时对每种物品i只有两种选择:装入背包或不装入背包称为0/1耆包问题 与装载问题不同的是0/1背包不能只装一部分要么选要么不选。
设 x i x_{i} xi表示物品i装入背包的情况 x i x_{i} xi0表示物品i没有被装入背包 x i x_{i} xi1表示物品i被装入背包 约束条件: ∑ i 1 n w i x i ≤ C x i ∈ { 0 , 1 } ( 1 ≤ i ≤ n ) \begin{array}{} \sum_{i1}^{n}w_{i}x_{i} \le C \\ x_{i}\in \left \{ 0,1 \right \}(1 \le i \le n) \end{array} ∑i1nwixi≤Cxi∈{0,1}(1≤i≤n) 目标函数 m a x ∑ i 1 n v i x i max\sum_{i1}^{n}v_{i}x_{i} maxi1∑nvixi 例有5个物品重量分别是{22654}价值分别为{63546}背包容量为10 定义一个(n1)(C1)的二维表dp[][] dp[i][j]表示把前i个物品装入背包中花费容量为j的情况下获得的最大价值
012345678910012345填表按只放第一个物品只放前2个只放前3个…一直到放完这样的顺序考虑(从小问题扩展到大问题)
只装第一个物品(横向是递增的背包容量)
0123456789100000000000001006666666662345
只装前2个物品 如果第2个物品重量比背包容量大那么不能装第2个物品情况和只装第1个一样 如果第2个物品重量小于背包容量那么 如果把物品2装进去(重量是2)那么相当于只把1装到(容量-2)的背包中如果不装2那么相当于只把1装到背包中取1和2的最大值
012345678910000000000000100666666666200669999999345
只装前3个物品 如果第3个物品重量比背包大那么不能装第3个物品情况和只装第1、2个一样。 如果第3个物品重量小于背包容量那么 如果把物品3装进去(重量是6)那么相当于只把1、2装到(容量-6)的背包中如果不装3那么相当于只把1、2装到背包中取1和2的最大值
01234567891000000000000010066666666620066999999930066999911111445
按这样的规律一行行填表直到结束现在回头考虑装了那些物品看最后一列1514说明装了物品5否则价值不会变化
012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515
小明的背包1
【题目描述】小明有一个容量为C的背包。这天他去商场购物商场一共有N件物品第i件物品的体积为 c i c_{i} ci价值为 w i w_{i} wi。小明想知道在购买的物品总体积不超过C的情况下所能获得的最大价值为多少请你帮他算算。 【输入描述】输入第1行包含两个正整数 NC表示商场物品的数量和小明的背包容量。 第 2~N1 行包含 2个正整数c,w表示物品的体积和价值。 1 ≤ N ≤ 1 0 2 1 \le N\le 10^2 1≤N≤102, 1 ≤ C ≤ 1 0 3 1 \le C\le 10^3 1≤C≤103, 1 ≤ w i , c i ≤ 1 0 3 1 \le w_{i},c_{i}\le 10^3 1≤wi,ci≤103 【输出描述】输出一行整数表示小明所能获得的最大价值。
DP状态设计
DP状态定义二维数组dp[][]大小为NxC dp[i][j]把前i个物品(从第1个到第i个)装入容量为j的背包中获得的最大价值。 把每个dp[i][j]看成一个背包:背包容量为j装1~i这些物品。最后得到的dp[N][C]就是问题的答案把N个物品装进容量c的背包的最大价值。
DP状态转移方程
递推计算到dp[i][j]分2种情况:
第i个物品的体积比容量j还大不能装进容量j的背包。那么直接继承前i-1个物品装进容量j的背包的情况即可:dp[i][j] dp[i-1][j]第i个物品的体积比容量j小能装进背包。又可以分为2种情况:装或者不装第i个 装第i个从前i-1个物品的情况下推广而来前i-1个物品是dp[i-1][j]。第i个物品装进背包后背包容量减少c[i]价值增加w[i]。有:dp[i][j] dp[i-1][j-c[i]] w[i]。不装第i个那么dp[i][j] dp[i-1][j]取1和2的最大值 状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - c[i]] w[i])
代码
#include bits/stdc.h
using namespace std;const int N 3011;
int w[N], c[N]; //物品的价值和体积
int dp[N][N];
int solve (int n, int C)
{for (int i 1; i n; i){for (int j 0; j C; j){if (C[i]j) //第i个物品比背包还大装不了dp[i][j] dp[i-1][j];else //第i个物品可以装dp[i][j] max(dp[i-1][j], dp[i-1][j-c[i]] w[i]);}}return dp[n][C];
}
int main()
{int n, C;cin n C;for (int i 1; i n; i){cin c[i] w[i];}memset(dp, 0, sizeof(dp)); //清0cout solve(n, C);return 0;
}空间优化滚动数组
把dp[][]优化成一维的dp[]以节省空间。 Dp[i][]是从上面一行dp[i-1]算出来的第i行只跟第i-1行有关系跟更前面的行没有关系! dp[i][j]max(dp[i-1][j],dp[i-1][j- c[i]] w[i]) 优化:只需要两行dp[0][]、dp[1][]用新的一行覆盖原来的一行交替滚动。 经过优化空间复杂度从O(NxC)减少为O©。
定义dp[2][j]:用dp[0][]和dp[1][]交替滚动。 优点:逻辑清晰、编码不易出错建议初学者采用这个方法 因为我们新一行的计算只与上一行有关所以两行重复使用即可 伪代码
int w[N], c[N]; //物品的价值和体积
int dp[2][N]; //替换int dp[][];
solve (int n, int C)
{now 0, old 1; //now指向当前正在计算的一行old指向旧的一行for (int i 1; i n; i ){//交替滚动now始终指向最新的一行if(c[i] j)dp[now][j] dp[old][j];elsedp[now][j] max(dp[old][j], dp[old][j - c[i]] w[i]);}return dp[now][C]; //返回最新的行
}自我滚动
因为状态转移每次只与上一层有关所以用一个一维数组就可以。 继续精简:用一个一维的dp[]就够了自己滚动自己。 dp[j]dp[j-c[i]]w[i] 为什么从大到小遍历看dp[j]dp[j-c[i]]w[i]这一状态转移是根据小的改大的如果先把小的改了那小的还会被用到数据就不对了所以从大到小
for (int i 0; i n; i ) //遍历每一件物品
{//遍历背包容量表示在上一层的基础上容量为j时第i件物品装或不装的最优解for (int j C; j c[i]; j --){dp[j] max(dp[j-c[i]] w[i], dp[j]);}
}j从小往大循环是错误的
0123456789dp[j]0066666666dp[j]0066696666
例如i2时上图的dp[5]经计算得到dp[5]9把dp[5]更新为9。
0123456789dp[j]0066696666dp[j]00666966126
下图中继续往后计算当计算dp[8]时得dp[8]dp[5]39312这个答案是错的。 错误的产生是滚动数组重复使用同一个空间引起的.
j从大到小循环是对的 例如i 2时首先计算最后的dp[9] 9它不影响前面状态的计算 1.
0123456789dp[j]0066666666dp[j]0066666669 0123456789dp[j]0066666669dp[j]0066666699
初始化细节
装满 dp[0]0其余赋值-INF;不装满全初始化为 0; 若一定要求装满: 则必有nsum(c[i]) i ∈ i \in i∈已选集合 所以dp[n-sum(c[i])] dp[0] 所以只有从dp[0]出发才合法那就把其他的设成无穷小。
//装满
memset (dp, -0x3f, sizeof(dp));
dp[0] 0;
//不装满
memset (dp, 0, sizeof(dp));
