找零问题描述：给定金额为n，面值为d1
设F(n)是总金额为n的最少硬币数
n>0时，F(n)=min{F(n-dj)}+1 (n>=dj)
n=0时，F(0)=0;
找零的关键代码如下：
int changeMaking(int D[],int m,int n) //m为D的len,n为金额
{int i;
F[0]=0;
for(i=1;
i<=n;
i++) //从1 到n的各个值所需的币数
{
int temp=10000,j=1;
while(j<=m and i>=D[j])
{temp=min(F[i-D[j]],temp);
j=j+1;
}
F[i]=temp+1;
}
return F[n];
}
完整代码实现：
#include
#define MAX 20
int c[MAX];
//存储所有币值
int F[MAX];
//存放1到n的各个值所需的币数int min(int x,int y)//取较小值函数
{
return (x=D[j])
{temp=min(F[i-D[j]],temp);
j=j+1;
}
F[i]=temp+1;
}
return F[n];
}
int main() {
int n,m;
printf("请输入有多少个纸币：");
scanf("%d", &n);
printf("请分别输入纸币的价值：");
for (int i = 1;
i <= n;
i++)
{
scanf("%d", &c[i]);
}
printf("请输入金额：");
scanf("%d", &m);
int number=changeMaking(c,n,m);
printf("一共需要%d个币\n",number);
int j=m,i,num=0;
int arr[MAX];
while(j>0)
{
for(i=n;
i>0;
i--)
{
if(j-c[i]>=0 and F[j-c[i]]==number-1) //要求j-c[i]>=0才有效，否则可能为负，而且F[]的值符合要求
{
arr[num++]=c[i];
j=j-c[i];
number=number-1;
break;
//找到符合要求的币值，则break
}
else{ continue;
}
}
}printf("各个币值为：");
for (int i = 0;
i 【动态规划之找零问题 —c++实现】效果图：
文章图片
OK，今天的算法就分享到这里喽。拜拜
