硬币找零&&爬楼梯&&猴子摘香蕉

硬币找零&&爬楼梯&&猴子摘香蕉

假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。

#include"CoinProblem.h"#include<iostream>int countNum=MAX;void CoinProblem(int *coin,int Length,int Value,int count){ if(Value==0){ if(countNum>count){ countNum=count; } return; } for(int i=0;i<Length; i++){ if(Value>=coin[i]){ CoinProblem(coin,Length,Value-coin[i],count+1); } }} #ifndef COIN_PROBLEM_H#define COIN_PROBLEM_H#define MAX 65535extern int countNum; void CoinProblem(int *coin,int Length,int Value,int count); #endif #include"CoinProblem.h"#include<iostream>int main(){ int coin[3]={1,3,5}; CoinProblem(coin,3,5,0); std::cout<<countNum<<std::endl; }

这些问题都是一类问题，你猴子摘香蕉、硬币找零、爬楼梯等。

这类问题的共同点就是你要问题解决问题，也就是说你要恰好把问是不多不少地解决，不管你怎么摘香蕉，不管你一次

是摘几个，你得把香蕉摘完。你得恰好找别人那么钱，不能多也不能少。爬楼梯也一样啰。。反下是解决问题。

这个不像背包问题，因为背包是不一定能装满的，也就是结束条件是不确定的。

但是我们不要管是不是恰好，因为我们采用了梯归。因为递归的好处是把所有能考虑的问题都考虑了，包括恰好解决问题和

把问题所要求的多，或者少。。

if(Value==0){ if(countNum>count){ countNum=count; } return; }

如上面的代码就是专门用来限制结束条件的，只有当我们找的钱恰好是那么多是，我们才会计数。

于是我们可能通过自己的限定条件来限制要计数的情况。

特注意的是：

​由于我自己的疏忽，导致在以前写这些代码的时候出了些小问题，以前我是这样写的

void CoinProblem(int *coin,int Length,int Value,int count){ if(Value==0){ if(countNum>count){ countNum=count; } return; } for(int i=0;i<Length; i++){ if(Value>=coin[i]){ CoinProblem(coin,Length,Value-coin[i],++count); } }}

看代码中红色的部分，这里成了++count,这里是改变了count的值，我这意思是改变了在这一次递归运算中的所有count的值，也就是说，i=0时

如count=2，同时也符合条件，也就是说进入那个条件判断语句，于是用++count时会发现count变成了3，这确实是我们所期望的，但是

如果下一次“归”回来后，i=1时，那时发现count一开始就是3了。不再是我们期望的2了。

于是正确的写法应该是这样：

void CoinProblem(int *coin,int Length,int Value,int count){ if(Value==0){ if(countNum>count){ countNum=count; } return; } for(int i=0;i<Length; i++){ if(Value>=coin[i]){ CoinProblem(coin,Length,Value-coin[i],count+1); } }} 来自为知笔记(Wiz)

转载于:https://www.cnblogs.com/yml435/p/4655519.html