AI时代，找源码已成为过去式，纪念我过去的十年0(回)
71天前
还有人吗2(回)
89天前会python真的可以为所欲为0(回)
569天前
这里还有人吗2(回)
754天前这里还有人吗0(回)
754天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
979天前#include <stdio.h> |
#include <stdlib.h> |
#define INF 100000000 |
#define MAXNUM 10000 |
#define MONEYKIND 100 |
int n,S; |
int V[MONEYKIND]; |
int min[MAXNUM],max[MAXNUM]; |
void dp(int*,int*); |
//递推方法函数声明 |
void print_ans(int*,int); |
//输出函数声明 |
int main() |
{ |
int i; |
printf("输入硬币的种数n(1-100):\n"); |
scanf("%d",&n); |
printf("输入要组合的钱数S(0-10000):\n"); |
scanf("%d",&S); |
printf("输入硬币种类：\n"); |
for(i=1; i<=n; i++) |
{ |
scanf("%d",&V[i]); |
} |
dp(min,max); |
printf("最小组合方案：\n"); |
print_ans(min,S); |
printf("\n"); |
printf("最大组合方案：\n"); |
print_ans(max,S); |
return 0; |
} |
void dp(int *min,int *max) |
//递推过程实现 |
{ |
int i,j; |
min[0] = max[0] = 0; |
for(i=1; i<=S; i++)//初始化数组 |
{ |
min[i]=INF; |
max[i]=-INF; |
} |
for(i=1; i<=S; i++) |
for(j=1; j<=n; j++) |
if(i>=V[j]) |
{ |
if(min[i-V[j]]+1<min[i]){ |
min[i]=min[i-V[j]]+1;//最小组合过程 |
//printf("%d\n",min[i]); |
} |
if(max[i-V[j]]+1>max[i]) |
max[i]=max[i-V[j]]+1;//最大组合过程 |
} |
} |
void print_ans(int *d,int S) |
//输出函数实现 |
{ |
int i; |
for(i=1; i<=n; i++) |
if(S>=V[i]&&d[S]==d[S-V[i]]+1) |
{ |
printf("%d-",V[i]); |
print_ans(d,S-V[i]); |
break; |
} |
} |
by: 发表于：2017-08-09 10:52:22 顶(0) | 踩(0) 回复
??
回复评论