Ⅰ C語言 砝碼稱重問題,高手進~~~~
這是耐鬧一道簡單的動態規劃題目.
它的做法是:
先只用第碧畝橋一種砝碼,看它能構成多少種重量,
再用前2種,看能構成多少種重量(不包括上面的那個)
接著前3種..
前4鍾...
前5種...
前6種...
所以有第一個for 循環
for ( i = 0; i < 6; i++ )
第2個for循環是表示第i種砝碼悔猛用多少個情況.
for ( j = 0; j < a[ i ]; j++ )
從0(不用)的情況到a[i]種.
事實上這里的終止條件應該為j<=a[i];因為可以用a[i]個第i種砝碼.
第3個循環是從1000開始,看哪個數字是能夠構成的.
f[ k - m[ i ] ] 表示大小為k-m[i]的重量是可以構成的,所以k-m[i]+m[i]即k也是可以構成的.
此時在判斷f[k].如果!f[k]成立,表示k為統計.則total++;
for ( k = 1000; k >= m[ i ]; k-- )
這是一道典型的簡單的動態規劃題目.
是演算法的一類題目.
建議先去學習一些動態規劃的知識再學習這個
Ⅱ C語言砝碼稱重
#include<stdio.h>
struct fama
{
int weight; int num;
}fama1[10];
int count(struct fama a[10],int k,int n)
{
int temp=0,m=0,p;
int w[10000]={0};
for(int i=k;i<n;i++)
{
for(int j=0;j<a[i].num;j++)
{
p=1; temp+=a[i].weight;
for(int x=0;x<m;x++)
{
if(temp==w[x])
p=0;
}
if(p) { w[m]=temp; m++; }
}
} return m; }
void main()
{ int n=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&fama1[i].weight,&fama1[i].num);
int maxnum=0;
for(i=0;i<n;i++)
maxnum+=count(fama1,i,n);
printf("%d\n",maxnum);
}
給分吧，速度
Ⅲ C語言砝碼稱重問題
這個題目粗看上去似乎不難,但是真寫似乎有點難度,代碼貼上,
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<memory.h>
/*a數組用於存儲從n個整型數
*據中取k個數字的數組下標值
**/
inta[100]={0};
/*data數組用於存儲實際的數據,也就是所有砝碼的
*重量
**/
intdata[4]={2,2,3,3};
/*sum數組用於保存再data中取k個樹的和,注意
*沒有唯一化處理,也就是說可能裡面存在重復
*唯一化處理使用函數unique;
**/
intsum[100]={0};
/*index_sum用於記錄sum中最後一個數據的索引值
**/
intindex_sum=0;
/*這是一個遞歸實現臘派雀,用於獲取從[start,length-num]的
*某一位數,這個位數對應了data數組的下標,num是從
*data中取幾位數的,fujia是一個附加參數,用於記錄當
*前獲取了幾位樹,從而方便操作數組a
**/
voidGetNumberNew(intstart,intlength,intnum,intfujia);
/*統計長度為length的sum數組中不重復元素的個數
**/
intunique(int[],intlength);
intmain()
{
//data數組長度
intlength=4;
for(inty=1;y<=length;y++)
{
/*從[0,num]中獲取y個數*/
GetNumberNew(0,length,y,y);
}
羨盯printf("%d",unique(sum,index_sum));
return0;
}
voidGetNumberNew(intstart,intlength,intnum,intfujia)
{
for(inti=start;i<=length-num;i++)
{
if(num>0)
{
a[num-1]=i;
/*從[i+1,length]中獲取num-1數
**/
GetNumberNew(i+1,length,num-1,fujia);
}
else
{
for(intx=0;x<fujia;x++)
{
sum[index_sum]+=data[a[x]];
}
index_sum++;
return;
}
}
}
intunique(intsum[],intlength)
{
inttemp=index_sum;
//printf("temp:%d",temp);
for(inti=0;i<length-1;i++)
{
for(intj=i+1;j<length;j++)
{
if(sum[i]==sum[j])
{
/*若有相同的數字則減1,並退出此次循環*/
temp--;
break;
}
}
輪早}
returntemp;
}