砝码称量问题,思维训练-->爱以走远转移
砝码称量现有1g、2g、3g、5g、10g、20g的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重量不超过1000克，且砝码只能放在天平的一端）
输入方式：a1 a2 a3 a4 a5 a6
(表示1g砝码有a1个，2g砝码有a2个，......20g砝码有a6个)
输出方式:Total=N
(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)
如:输入:1 1 0 0 0 0
输出:Total=3 表示可以称出1g,2g,3g三种不同的重量。
在Turbo C2.0集成环境下运行.
----------------解决方案--------------------------------------------------------
LZ发错地方了
----------------解决方案--------------------------------------------------------
回复：（菜鸟上路）LZ发错地方了[em04]
哦,那要发在哪呢/能不能告诉我一下呀
----------------解决方案--------------------------------------------------------
一个比较简单的算法,效率不高,但应付楼主要求的数据量应该绰绰有余了
程序代码：
/**
* Written by [url=http://eastsun.javaeye.com]Eastsun[/url]
*/
#include<stdio.h>
#include<conio.h>
#define MAX 1000
#define SIZE 6
char flags[MAX+1];
int w[] ={1,2,3,5,10,20};
void check(int a[],int len){
int i,j;
if(len<=0) return;
check(a,len-1);
for(i=1;i<=a[len-1];i++)
for(j=MAX;j>=0;j--) if(flags[j]) flags[j+w[len-1]] =1;
}
int computer(int a[]){
int n,s=0;
flags[0] =1;
for(n=1;n<=MAX;n++) flags[n] =0;
check(a,SIZE);
for(n=1;n<=MAX;n++) s += flags[n];
return s;
}
int main(){
int a[SIZE],n;
printf(\"Input a1~a6:\");
for(n=0;n<SIZE;n++) scanf(\"%d\",&a[n]);
printf(\"Total: %d\",computer(a));
getch();
}
----------------解决方案--------------------------------------------------------
程序在gcc下编译通过,应该在TC下也没问题.
----------------解决方案--------------------------------------------------------
我感觉用穷举能做
----------------解决方案--------------------------------------------------------
我用的应该算动态规划吧
----------------解决方案--------------------------------------------------------
谢谢大家呀.
----------------解决方案--------------------------------------------------------