文档介绍：。
实验报告
学号：姓名：班级：
课程名称算法设计与分析实验课时 2
实验项目最少硬币问题实验时间
设有 n 种不同面值的硬币，各硬币的面值存于数组 T[1:n] 中。现
要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于
实验目的数组 Coins[1:n] 中。
对任意钱数 0 ≤m ≤20001 ，设计一个用最少硬币找钱 m 的方
法。
实验环境 Visual C++
一、算法策略
对于给定的 1≤n≤10 ，硬币面值数组 T和可以使用的各种面值的
硬币个数数组 Coins ，以及钱数 m ，0 ≤m ≤20001 ，计算找钱 m 的
实验内容最少硬币数。
（算法、程
序、步骤和二、算法设计（步骤）
方法）算法思想：
（1）动态规划实现
长度为 m 的数组 f[1...m] 中存放一系列子结果，即 f[i] 为要凑
的钱数为 i 时，所需的最少硬币数，则 c[m] 为所求 ; 当要找的钱数
-可编辑修改 -
。
i(1<i<m) 与当前所试探的硬币面值 k 相等时，结果为 1 ，即
c[i]=1 ；当 i 大于当前所试探硬币面值 k 时，若 f[i] 为 0 ，即还未
赋过值，且 c[i-k] 不为 0 ，即从 i 元钱中刨去 k 元后剩下的钱数可以
找开，则 c[i]=c[i-k]+1 ，若 f[i] 不为 0 ，即已赋过值，则 f[i] 为 f[i-k]+1
和 f[i] 中较小的。
（2）硬币问题就是一个多重背包问题。
（3）动态迁移方程为 dp[k] = min{dp[k-t[i]]+1,dp[k]}
将第 i 个硬币拿出去得到的一个最少的找硬币数 +1 ，和原硬币
数相比最小的那个就是结果。
（4）另外一种思路，可以将所有的硬币价值都放在一个数组，就
变成了 0-1 背包问题，所需考虑的就是放不放的问题。
算法步骤：
#include<iostream>
using namespace std;
int min(int a,int b);
int main()
{
-可编辑修改 -
。
int n; //n 种不同面值的硬币
int m;
int i , j ,k;
cout<<" 请输入有几种不同的面值 :";
cin>>n;
int *t =new int[n+1]; // 硬币的面值存
放在 t 数组中 -- 价值
int *coin = new int [n+1]; // 可以使用的硬