动态规划(Dynamic Programming,DP)一般是多阶段决策问题,把一个复杂问题分解为相对简单的子问题,再一一解决,得到原复杂问题的最优解。
求解DP问题的步骤:定义状态、状态转移、算法实现。
DP问题可以分为线性和非线性的。
线性DP。线性DP有两种方法:顺推与逆推。在线性DP中,常常用“表格”来处理状态,用表格这种图形化工具可以清晰易懂地演示推导过程。
非线性DP。例如:树形DP,建立在树上,也有两个方向:1)根->叶,根传递有用的信息给子节点,最后根得出最优解。2)叶->根,根的子节点传递有用的信息给根,最后根得出最优解。
最少硬币问题
有n种硬币,面值为v1,v2,...,vn,数量无限。输入非负整数s,选用硬币,使其和为s。要求输出最少的硬币组合。
解决:定义一个数组 int Min[MONEY],其中Min[i]是金额j对应的最少硬币数量。
初始值Min[0](即总金额为0时)需要0个硬币
金额为1时,Min[1]=Min[0]+1=Min[1-1]+1;
金额为2时,Min[2]=Min[1]+1=Min[2-1]+1;.......
金额为5时,Min[5]=Min[5-5]+1;// 有五元的面值,总金额减5,加1个(五元)硬币
金额为6时,Min[6]=Min[6-5]+1;..........
递推式:Min[i]=min(Min[i],Min[i-type[j]]+1;
(为什么是Min[i]?因为一开始总金额先(取)减type[0]的面额,得到Min[i];然后再(取)减type[1]面额,以此类推,比较之后,才取最少硬币数量)
#include <bits/stdc++.h>
using namespace std;
const int MONEY = 251;//定义最大金额
const int VALUE = 5;//5种硬币
int type[VALUE] = { 1,5,10,50,100 };//5种面值
int Min[MONEY];//每个金额对应最少的硬币数量
void minCoin() {
for (int i = 0; i < MONEY; i++) {
Min[i] = INT_MAX;//初始值为无穷大
}
Min[0] = 0;
for (int i = 0; i < VALUE; i++) {
for (int j = type[i]; j < MONEY; j++) {
Min[j] = min(Min[j], Min[j - type[i]] + 1);//递推式
}
}
}
int main()
{
int m = 0;
cin >> m;
minCoin();
cout << Min[m] << endl;
return 0;
}
打印最少硬币的组合
在最少硬币问题中,增加一个记录表minPath[i],记录金额 j 需要的最后一个硬币,利用minPath倒推,就能得到所有的硬币。
#include <bits/stdc++.h>
using namespace std;
const int MONEY = 251;//定义最大金额
const int VALUE = 5;//5种硬币
int type[VALUE] = { 1,5,10,50,100 };//5种面值
int Min[MONEY];//每个金额对应最少的硬币数量
int minPath[MONEY] = { 0 };//记录最小硬币的路径
void minCoin() {
for (int i = 0; i < MONEY; i++) {
Min[i] = INT_MAX;//初始值为无穷大
}
Min[0] = 0;
for (int i = 0; i < VALUE; i++) {
for (int j = type[i]; j < MONEY; j++) {
if (Min[j] > Min[j - type[i]] + 1) {
minPath[j] = type[i];//记录
Min[j] = Min[j - type[i]] + 1;//递推式
}
}
}
}
//打印硬币组合
void printCoin(int* minPath, int s) {
while (s) {
cout << minPath[s] << ' ';
s = s - minPath[s];
}
}
int main()
{
int m = 0;
cin >> m;
minCoin();
cout << Min[m] << endl;
printCoin(minPath, m);
return 0;
}
所有硬币组合数1
有n种硬币,面值为v1,v2,...,vn,数量无限。输入非负整数s,选用硬币,使其和为s。要求输出可能的硬币组合。
计算所有硬币组合数:
初始状态:金额为0,组合数为0
金额为i时,dp[i]=dp[i-type[0]]+dp[i-type[1]]+dp[i-type[2]]....
金额为i,可以是dp[i-1]加1个1元硬币,dp[i-5]加1个5元硬币.......
注:没有考虑硬币数量的限制。
代码如下:
#include <bits/stdc++.h>
using namespace std;
const int MONEY = 251;//定义最大金额
const int VALUE = 5;//5种硬币
int type[VALUE] = { 1,5,10,50,100 };//5种面值
int dp[MONEY] = { 0 };//每种金额对应的组合数
void countCoin() {
dp[0] = 1;
for (int i = 0; i < VALUE; i++) {
for (int j = type[i]; j < MONEY; j++) {
dp[j] = dp[j] + dp[j - type[i]];
}
}
}
int main()
{
int m = 0;
cin >> m;
countCoin();
cout << dp[m] << endl;
return 0;
}
所有硬币组合数1
有5种面值的硬币,即1、5、10、25、50。输入一个钱数s,输出组合方案的数量。s<=250; num<=100。
dpcoin[i][j]是用j个硬币实现金额i的方案数量。利用dpcoin[i][j]可以找到某金额对应的最少和最多硬币数量。文章来源:https://www.toymoban.com/news/detail-734535.html
状态转移方程式:dpcoin[k][j] += dpcoin[k - type[i]][j - 1];文章来源地址https://www.toymoban.com/news/detail-734535.html
#include <bits/stdc++.h>
using namespace std;
const int MONEY = 251;//定义最大金额
const int VALUE = 5;//5种硬币
int type[VALUE] = { 1,5,10,25,50 };//5种面值
//考虑硬币的数目num
const int COIN = 101;//不超过100个硬币
int dpcoin[MONEY][COIN] = {0};//DP转移矩阵
int CoinCombination(int s) {
dpcoin[0][0] = 1;
for (int i = 0; i < VALUE; i++) {
for (int j = 1; j < COIN; j++) {
for (int k = type[i]; k < MONEY; k++)
dpcoin[k][j] += dpcoin[k - type[i]][j - 1];
}
}
int ans[MONEY] = { 0 };
for (int i = 0; i < MONEY; i++)
for (int j = 0; j < COIN; j++)
ans[i] += dpcoin[i][j];//对每个金额计算组合方案数目
return ans[s];
}
int main()
{
int m = 0;
cin >> m;
cout << CoinCombination(m) << endl;
return 0;
}
到了这里,关于【动态规划】基础DP--硬币组合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!