解题1
//---------------------------------------------------------------------------
题目：
设有1g，2g，3g，5g，10g，20g的砝码若干枚（其总重量＝<1000g），要求：
输入a1，a2，a3，a4，a5，a6（表示1g的砝码有a1个，2g的a2个，……，20g的砝码a6个）
输出total＝n（n表示用这些砝码能够称出的不同重量的个数，但不包括一个砝码也不取用的情况）
//-------------------------------------------------------------------------
十分差的穷举我不写了，首先写一个可以上的了台面的穷举。
#include <iostream.h>
int main(int argc, char* argv[])
{
int a[6];
bool qj[1001]={false};
int n,n1,n2,n3,n4,n5,n6,tl=0;
for (n=0;n<=5;n++)
cin>>a[n];
for (n1=0;n1<=a[0];n1++)
for (n2=0;n2<=a[1];n2++)
for (n3=0;n3<=a[2];n3++)
for (n4=0;n4<=a[3];n4++)
for (n5=0;n5<=a[4];n5++)
for (n6=0;n6<=a[5];n6++)
qj[n1+2*n2+3*n3+5*n4+10*n5+20*n6]=true;
qj[0]=false;
for (n=0;n<1001;n++)
if (qj[n]==true) ++tl;
cout<<”total=”<<tl;
getchar();
getchar();
return 0;
}
//---------------------------------------------------------------------------
写这个东西，是为了说明一点，就是引出本文乃至本系列中很重要的一点。数组下标利用。
bool qj[1001]设置了这么一个bool数组，就是为了利用其下标。我把解都放入了下标里。因为题目中有一点说：其总重量＝<1000g。所以一般情况来讲。不可能超出时间限制。
记住没有永远的算法，只有永恒的变化。
上面的穷举显然在某些方面不合适（如果题目改变的话）。因为穷举有时实效不是很高。所以我们需要优化。从思想上进行优化。
先给出代码：
#include <iostream.h>
int main(int argc, char* argv[])
{
int a[6],val[6];
bool qj[1001]={false};
int n,n1,n2,n3,n4,n5,n6,tl=0;
for (n=0;n<=5;n++)
cin>>a[n];
qj[0]=true;
val[0]=1;val[1]=2;val[2]=3;val[3]=5;val[4]=10;val[5]=20;
n=a[0]+2*a[1]+3*a[2]+5*a[3]+10*a[4]+20*a[5];
for (n3=0;n3<=5;++n3)
for (n2=1;n2<=a[n3];++n2)
for (n1=n;n1>=0;--n1)
if (qj[n1]) qj[n1+val[n3]]=true;
qj[0]=false;
for (n=0;n<1001;n++)
if (qj[n]==true) ++tl;
cout<<”total=”<<tl;
getchar();
getchar();
return 0;
}
这种方法很不错。思想抓住了两点：
1、反正你的解就在qj[1001]中
2、砝码先加和后加的次序无关
懂得了思想剩下的就只有一些编程上的小问题了。
你知道为什么开始要
qj[0]=true;这个属于小技巧。为了让下面的for语句可以顺利运行。
三条for语句都在干什么？
第一条for语句是利用了思想2。因为与砝码的次序无关，所以我们可以根据一个个砝码可以生成的值作文章。动态规划，差不多了。
