韩国网站源码下载,网站买卖需要注意什么,七星彩网站建设,软件公司主要做哪些文章目录1. 问题描述2. 问题分析2.1 回溯法求解2.2 DP状态转移方程法2.3 DP状态转移表法1. 问题描述
找零问题#xff0c;在贪心算法讲过。但是贪心不一定能得出最优解。假设有几种不同币值的硬币v1#xff0c;v2#xff0c;.……vn#xff08;单位是元#xff09;。如果…
文章目录1. 问题描述2. 问题分析2.1 回溯法求解2.2 DP状态转移方程法2.3 DP状态转移表法1. 问题描述
找零问题在贪心算法讲过。但是贪心不一定能得出最优解。假设有几种不同币值的硬币v1v2.……vn单位是元。如果要支付w元求最少需要多少个硬币。比如有3种不同的硬币1元、3元、5元我们要支付9元最少需要3个硬币3个3元的硬币。
2. 问题分析
2.1 回溯法求解
/*** description: 找零钱需要张数最少回溯法* author: michael ming* date: 2019/7/20 22:50* modified by:*/
#include iostream
#define N 3
int rmb[N] {1,9,10};//钞票面额
int amount[N];
int minAmount[N];
using namespace std;
void exchange(const int targetMoney, int curMoney, int minPiece, int piece)
{if(curMoney targetMoney)//超过目标返回return;if(curMoney targetMoney)//达到目标金额{if(piece minPiece){minPiece piece;//更新最小张数for(int i 0; i N; i)minAmount[i] amount[i];//获取每张钞票的张数}return;}for(int i 0; i N; i){//递归调用,拿取每张面额的钞票amount[i];exchange(targetMoney,curMoneyrmb[i],minPiece,piece1);amount[i]--;//恢复上次的状态}
}
int main()
{int minPiece 65535, piece 0,targetMoney 18, curMoney 0;exchange(targetMoney,curMoney,minPiece,piece);cout 凑成 targetMoney 元最少需要 minPiece 张(枚)。 endl;int i 0;while(i N){if(minAmount[i] ! 0)cout minAmount[i] 个 rmb[i] ;i;}cout endl;cout ---------------------- endl;
}2.2 DP状态转移方程法
由于上面的钞票面额可能不止3种递归树是多叉树所以状态转移表法画起回溯的递归图比较麻烦我们采用状态转移方程法。
状态转移方程如下
minPiece(targetMoney) 1 min{minPiece(targetMoney-rmb[0]), ... , minPiece(targetMoney-rmb[N-1])}targetMoney 18;//目标金额 rmb[N] {1,9,10};//钞票面额 对于题目的情况代入具体数值状态转移方程如下
minPiece(18) 1 min{minPiece(18-1), minPiece(18-9) , minPiece(18-10)} 1 min{minPiece(17),minPiece(9),minPiece(8)}DP递归备忘录代码如下
/*** description: 找零钱需要张数最少* author: michael ming* date: 2019/7/20 18:35* modified by: */
#include iostream
#include algorithm
#include memory.h#define N 3
const int targetMoney 18;//目标金额
int rmb[N] {1,9,10};//钞票面额
int mem[targetMoney1];//备忘录存放最小张数
using namespace std;
int minP(int Money)
{if(Money 0)//超过目标返回很大的张数表示不可能凑成return 65535;if(Money 0)//达到目标金额return 0;if(mem[Money] 0)//计算过了直接读取备忘录return mem[Money];int minAmount[N];memset(minAmount,65535,N*sizeof(int));for(int i 0; i N; i){//递归调用,拿取每张面额的钞票minAmount[i] minP(Money-rmb[i]);}sort(minAmount,minAmountN);mem[Money] minAmount[0]1;//记录最小的张数return mem[Money];
}
int main()
{cout 凑成 targetMoney 元最少需要 minP(targetMoney) 张(枚)。 endl;//如何打印出选取钞票的面额和张数
}2.3 DP状态转移表法
/*** description: 找零钱需要张数最少,dp状态表法* author: michael ming* date: 2019/7/21 20:01* modified by: */
#include iostream
#include algorithm
#include memory.h#define N 3
const int targetMoney 18;//目标金额
int rmb[N] {1,9,10};//钞票面额,从小到大
using namespace std;
void exchange(int Money)
{int maxPiece targetMoney/rmb[0];//最大张数int i, j, k;int (*states)[targetMoney1] new int [maxPiece][targetMoney1];//memset(states,65535,maxPiece*(targetMoney1)*sizeof(int));//上面错误memset一般只付0或极大值for(i 0; i maxPiece; i)for(j 0; j targetMoney; j)states[i][j] 65535;//初始化for(k 0, j 0; j targetMoney; j){if(k N j rmb[k]){//初始化第一行数据states[0][j] 1;//一张rmbk;}}for(i 1; i maxPiece; i)//动态规划{for(j 0; j targetMoney; j)//上面一行的数据考下来states[i][j] states[i-1][j];for(j 0; j targetMoney; j){if(states[i-1][j] ! 65535){for(k 0; k N; k){if(jrmb[k] targetMoney states[i-1][jrmb[k]] states[i-1][j]1)states[i][jrmb[k]] states[i-1][j]1;}}}}cout 凑成 targetMoney 元最少需要 states[maxPiece-1][targetMoney] 张(枚)。 endl;//------------打印选择的信息---------------------------for(i maxPiece-1; i 1 states[i][targetMoney] states[i-1][targetMoney]; --i);//此时i等于最早出现的答案处的行for(j targetMoney; j 0; ){if(i ! 0){for(k 0; k N; k){if(states[i-1][j-rmb[k]] states[i][j]-1){cout 1张 rmb[k] ;j j-rmb[k];i--;break;}}}else{cout 1张 j ;break;}}delete [] states;//释放资源
}
int main()
{exchange(targetMoney);return 0;
}
