dw1213_1.cpp

问题描述：某国家的硬币体系包含N种面值（其中一定有面值为1的）

#include<iostream.h>
#include<stdlib.h>
const int N=10;
const int P=1000;
void main()
{
	int value[N];//各种面值大小
	int i;//阶段变量
	int S;//状态变量
	int j;//决策变量
	int number[N][P+1];//在各种状态下的最优解
    int total[N][P+1];//在各种状态下硬币的总数
	int n,p;


	cout<<"请输入不同面值的数目:";cin>>n;
	cout<<"请输入各种面值大小:";
	for(i=0;i<n;i++)
			cin>>value[i];
   for(i=0;i<n-1;i++)
		for(j=i+1;j<n;j++)
			if(value[i]>value[j])
			{int temp1=value[i];
			value[i]=value[j];
			value[j]=temp1;
			}
cout<<"请输入要买商品的价格:";cin>>p;
	if(p<0||p>P)exit(0);
for(S=0;S<p+1;S++)
{number[0][S]=S/value[0];
total[0][S]=value[0]*number[0][S];
}
for(i=1;i<n;i++)
for(S=0;S<p+1;S++)
{number[i][S]=0;
total[i][S]=total[i-1][S];
for(j=0;j<=S/value[i];j++)
{
	int temp=j+total[i-1][S-value[i]*j];
		if(temp<total[i-1][S])
		{total[i][S]=temp;
			number[i][S]=j;
		}
}
}
int x[N];
int Value=p,mark=-1;
for(i=n-1;i>=0;i--)
{x[i]=number[i][Value];if(x[i]!=0)mark=0;
Value=Value-value[i]*x[i];
}
if(mark!=-1)
for(i=0;i<n;i++)
cout<<"面值为"<<value[i]<<"的硬币需要"<<x[i]<<"枚"<<endl;
else cout<<"无解"<<endl;

}