问题：有面值个不同的若干种面币，要找某一具体的零钱数目，求出使用面币的最少数量？
本题采用动态规划求解，动态规划最主要的是要找到问题的状态和状态转移方程，然后根据前面已有的状态去求解后面的状态，将一个大的问题分解成若干小的子问题去解决。
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int money;
cout<<"要找的零钱是：";
cin>>money;
int size;
int values[10];
cout<<"零钱有多少种：";
cin>>size;
cout<<"每种零钱的面值是：";
for(int i=0;i<size;i++)
cin>>values[i];
int coinused[money+1];
coinused[0]=0;
int mincoin=0;
for(int m=1;m<=money;m++)//从一到要找的零钱数遍历一遍
{
mincoin=m;//最少的面币的数量
for(int j=0;j<size;j++)//遍历面币的值
{
if(values[j]<=m)//若j面币可以使用
mincoin=min(mincoin,coinused[m-values[j]]+1);//比较使用后的最小值
}
coinused[m]=mincoin;//将所有的状态存储起来
}
cout<<"最少面币的数量是："<<coinused[money]<<endl;
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-33929.html
