main.cpp

来自「我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:」· C++ 代码 · 共 130 行

/*************************************************************************************

  75. (钱币系统问题) 某钱币系统由 k (k≤20) 种硬币组成, 币值依次为 a[1],
 a[2],...,a[k], 其中 a[i] (i=1,2,...,k) 为互不相同的正整数, 且依降序排列,
 a[1]≤200. 给定某整数币值 n(n≤3000), 要求用最少枚数的硬币表示这个币值.
    输入: 用文件输入已知数据, 格式为:
      第 1 行: k (硬币种数)
      第 2 行: a[1] a[2] ... a[k] (各币值用空格隔开,已按降序排列好)
      第 3 行: n (给定的币值)
    输出: 直接在屏幕上输出结果. 如果该钱币系统无法表示币值 n,应输出'No',
 否则按以下格式输出:
      第 1 行: 最少钱币枚数 r.
      第 2 行: 输出若干形如 m*n 的表达式, m 为币值, n为使用该币值的枚数.
 各式第 2 个因子之和应等于 r, 各式乘积之和应等于 n.
    例: 设 (a[1],a[2],a[3])=(5,2,1),  n=12,  则应输出
       3
       5*2  2*1.

  分析:求最优化组合问题可以用动态规划算法
  用贪心算法,可以得到比较小的结果,但是不一定最小.



  ***********************************************************************************/

#include <stdio.h>
#include <malloc.h>

void main()
{
	int i,j;
	int s,n;
	int *val,**ts,**vs,*vx;
	FILE *fp;

	fp = fopen("input.txt","r");

	fscanf(fp, "%d", &n);
	printf("硬币种类总数: %d",n);
	
	val = (int*) malloc(n*sizeof(int));
	vx = (int*) malloc(n*sizeof(int));
	printf("%d种硬币的币值:\n",n);
	for(i=0; i<n; i++)
	{
		fscanf(fp,"%d",&val[i]);
		printf("%d ",val[i]);
	}
	fscanf(fp,"%d",&s);
	printf("兑换金额: %d",s);
	fclose(fp);

	ts = (int**)malloc(n*sizeof(int*));
	vs = (int**)malloc(n*sizeof(int*));
	for(i=0; i<n; i++)
	{
		ts[i] = (int*)malloc((s+1)*sizeof(int));
		vs[i] = (int*)malloc((s+1)*sizeof(int));
	}

	for(i=0; i<n; i++)
	{
		for(j=0; j<=s; j++)
		{
            if(i==0 && j>0)
			{
				ts[i][j] = j;
				vs[i][j] = j;
			}
			else if(j == 0)
			{
				ts[i][j] = 0;
				vs[i][j] = 0;
			}
			else if((j < val[i]) && (j > 0) && (i > 0))
			{
				ts[i][j] = ts[i-1][j];
				vs[i][j] = 0;
			}
			else if((j >= val[i]) && (j > 0) && (i > 0))
			{
				int temp,k;

				ts[i][j] = ts[i-1][j];
				vs[i][j] = 0;
				temp=j / val[i];
				for(k=1; k<=temp; k++)
				{
					if(ts[i-1][j-k*val[i]]+k < ts[i][j])
					{
						ts[i][j] = ts[i-1][j-k*val[i]] + k;
						vs[i][j] = k;
					}
				}
			}
		}
	}

	{
		int q = s;
		vx[n-1] = vs[n-1][q];
		for(i=n-2; i>=0; i--)
		{
			int temp;
			temp = q-vx[i+1] * val[i+1];
			vx[i] = vs[i][temp];
			q = temp;
		}
	}

	fp = fopen("output.txt","w");
	printf("所需钱币总数: %d \n",ts[n-1][s]);
	fprintf(fp,"%d\n",ts[n-1][s]);
	for(i=0; i<n; i++)
	{
		printf("%d ",vx[i]);
		if(vx[i])
		{
			fprintf(fp, "%d*%d ", val[i], vx[i]);
		}
	}
	printf("\n");
	fprintf(fp,"\n");

	fclose(fp);
	free(val);
	for(i=0; i<n; i++)
	free(ts[i]);
	free(ts);
}