题目描述
设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。 对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。
输入
第一行中只有1 个整数给出n的值,第2 行起每行2 个数，分别是T[j]和Coins[j]。最后1 行是要找的钱数m。
输出
最少硬币数,无解时输出-1
样例输入
3
1 3
2 3
5 3
18
样例输出
5
这道题是一道动态规划的题目，半天想不明白要怎么下手，于是乎按照自己的思路解题：
将数组从大到小排序，用快排；
然后在数组中，判断找零数 m 是否大于硬币的数值，其对应硬币是不是被用完了；
如果满足上面的条件，则该数值的硬币是找零的其中之一 ，m减该数值得到新的零钱数；
重复进行上面的操作，如果最后可以得到 m 等于 0，则输出最小硬币数，否则，输出-1.
先看看代码：
typedef struct {
int T;
int Coins;
}Mo;
bool cmp(Mo a, Mo b){
return a.T > b.T ;
}
int ChangeMaking(int m, int n, Mo *a){
sort(a,a+n,cmp);
int flag = 0;
for(int i = 0; i < n; i++){
while(a[i].Coins > 0 && m - a[i].T >= 0){
m -= a[i].T ;
flag ++;
a[i].Coins --;
}
}
if(flag != 0 && m == 0) return flag;
else return -1;
}
你也觉得没有什么毛病，对吧？那就大错特错了。看这个例子：
设找零数 m = 8，有 1 个 5 ，2 个 4， 1 个 2。 这个例子看简单，看得出最小的硬币数是2个（2个4），但是按照上述的算法那么就会无解，与正确答案相矛盾。
所以，我们还是老老实实学习动态规划的算法，对此题作解。
下列是完整的代码。
代码
#include<iostream>
using namespace std;
int T[11],Coins[11];
int main(){
int n,m;
cin>>n;
for(int i = 1; i <= n; i++){
cin>>T[i]>>Coins[i];
}
cin>>m;
int dp[20001];
for(int i = 1; i < 20001; i++){
dp[i] = 101;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= Coins[i] ; j++ ){
for(int k = m; k >= T[i]; k --){
dp[k]=min(dp[k-T[i]] + 1,dp[k]);
}
}
}
if(dp[m] == 101) cout<<"-1"<<endl;
else cout<<dp[m]<<endl;
return 0;
}
思路
用了动态规划的算法；
此题的详细思路会在后续版本给出。
题目描述
Several coins are placed in cells of an n×m board. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location.
输入
The fist line is n,m, which 1< = n,m <= 1000.
Then, have n row and m col, which has a coin in cell, the cell number is 1, otherwise is 0.
输出
The max number Coin-collecting by robot.
样例输入
5 6
0 0 0 0 1 0
0 1 0 1 0 0
0 0 0 1 0 1
0 0 1 0 0 1
1 0 0 0 1 0
样例输出
5
代码
#include<iostream>
using namespace std;
int Coor[1000][1000];
int main(){
int N, M;
cin>>N>>M;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin>>Coor[i][j];
if(i == 1 && j > 1) Coor[1][j] += Coor[1][j-1];
if(j == 1 && i > 1) Coor[i][1] += Coor[i-1][1];
if(i > 1 && j > 1) Coor[i][j] += max(Coor[i][j-1],Coor[i-1][j]);
}
}
cout<<Coor[N][M]<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
思路
动态规划问题；
令F( i , j )为机器人截止到第 i 行第 j 列单元格 ( i , j ) 能够收集到的最大硬币数, 有如下递推式：
值得注意的是：递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。
我第一次用了递归的方式，出现了 Time Limit Exceeded ,普通循环修正以后，便可以通过。
但可以 利用上面的公式，我们可以通过逐行或者逐列的方式填充 n 乘以 m 表以求得F( i , j )。
算法—Coin Changing（最少硬币数）和币值最大化问题
原文：https://www.cnblogs.com/ynog/p/12770347.html