【动态规划】基础DP--硬币组合

这篇具有很好参考价值的文章主要介绍了【动态规划】基础DP--硬币组合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划(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]可以找到某金额对应的最少和最多硬币数量。

状态转移方程式: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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法竞赛备赛之动态规划训练提升,DP基础掌握

    01背包问题是在M件物品中选择若干件放在空间为W的背包中,每件物品的体积为W1,W2至Wn,价值为P1,P2至Pn,01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。 01背包问题常常采用动态规划的方法去求解,状态转移方程为:F(W,i)=max{F(W,

    2024年02月08日
    浏览(43)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(42)
  • acwing算法基础之动态规划--数位统计DP、状态压缩DP、树形DP和记忆化搜索

    暂无。。。 暂无。。。 题目1 :求a~b中数字0、数字1、…、数字9出现的次数。 思路:先计算1~a中每位数字出现的次数,然后计算1~b-1中每位数字出现的次数,两个相减即是最终答案。 那么,如何计算1~a中每位数字出现的次数呢? 首先,将a的每一位存入向量num中,例如a=123

    2024年02月04日
    浏览(51)
  • Problem P09. [算法课动态规划] 换硬币

    这将会是一个系统性的算法学习专栏,编程语言为C++,适用于刚开始学算法的学生和博友,建议需要的朋友收藏订阅,是免费的,希望对大家能够有所帮助。 动态规划当前状态和之前状态息息相关。比如这题:组成硬币,已经组成好的硬币x加上面值为y的硬币就可以组成好

    2024年02月22日
    浏览(61)
  • DP算法:动态规划算法

    (1)确定初始状态 (2)确定转移矩阵,得到每个阶段的状态,由上一阶段推到出来 (3)确定边界条件。 蓝桥杯——印章(python实现) 使用dp记录状态,dp[i][j]表示买i张印章,凑齐j种印章的概率 i表示买的印章数,j表示凑齐的印章种数 情况一:如果ij,不可能凑齐印章,概

    2024年02月07日
    浏览(51)
  • 算法——动态规划(DP)——递推

    动态规划常用于解决优化问题。 动态规划通常以自底向上或自顶向下的方式进行求解。 自底向上的动态规划从最简单的子问题开始,逐步解决更复杂的问题,直到达到原始问题。 自顶向下的动态规划则从原始问题出发,分解成子问题,并逐步求解这些子问题。 动态规划算法

    2024年01月20日
    浏览(57)
  • ★动态规划(DP算法)详解

    什么是动态规划:动态规划_百度百科 内容太多了不作介绍,重点部分是无后效性,重叠子问题,最优子结构。 问S-P1和S-P2有多少种路径数,毫无疑问可以先从S开始深搜两次,S-P1和S-P2找出所有路径数,但是当这个图足够大,那就会超时。 动态规划旨在用 空间换时间 ,我们

    2024年02月04日
    浏览(50)
  • 动态规划(DP)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 动态规划(Dynamic Programming,DP)是一种用来解决一类最优化问题的算法思想。简单来说,动态规划将一个复杂的问题分解成若干个子

    2024年02月05日
    浏览(47)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(48)
  • 【算法】动态规划(dp问题),持续更新

    介绍本篇之前,我想先用人话叙述一般解决动态规划问题的思路: 动态规划的问题,本身有许多产生结果的可能,需要在具体题目下得到满足某个条件的解。 如何得到呢? 我们就需要根据这个具体问题,建立一个状态表( dp 表 ),在这张 dp 表中的每一个位置的数据都有明

    2024年02月04日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包