本文目錄一覽：
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語言砝碼稱重
#includestdio.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;in;i++)
{
for(int j=0;ja[i].num;j++)
{
p=1; temp+=a[i].weight;
for(int x=0;xm;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;in;i++)
scanf(“%d%d”,fama1[i].weight,fama1[i].num);
int maxnum=0;
for(i=0;in;i++)
maxnum+=count(fama1,i,n);
printf(“%d\n”,maxnum);
}
給分吧，速度
C語言砝碼稱重問題
這個題目粗看上去似乎不難,但是真寫似乎有點難度,代碼貼上,
#includestdio.h
#includestdlib.h
#includestring.h
#includememory.h
/*a數組用於存儲從n個整型數
* 據中取k個數字的數組下標值
* */
int a[100]={0};
/*data數組用於存儲實際的數據,也就是所有砝碼的
* 重量
* */
int data[4]={2,2,3,3};
/*sum數組用於保存再data中取k個樹的和,注意
* 沒有唯一化處理,也就是說可能裏面存在重複
* 唯一化處理使用函數unique;
* */
int sum[100] = {0};
/*index_sum用於記錄sum中最後一個數據的索引值
* */
int index_sum = 0;
/*這是一個遞歸實現,用於獲取從[start,length-num]的
* 某一位數,這個位數對應了data數組的下標,num是從
* data中取幾位數的,fujia是一個附加參數,用於記錄當
* 前獲取了幾位樹,從而方便操作數組a
* */
void GetNumberNew(int start, int length, int num, int fujia);
/*統計長度為length的sum數組中不重複元素的個數
* */
int unique(int[], int length);
int main()
{
//data數組長度
int length = 4;
for(int y = 1; y = length; y++)
{
/*從[0,num]中獲取y個數*/
GetNumberNew(0, length, y, y);
}
printf(“%d”,unique(sum, index_sum));
return 0;
}
void GetNumberNew(int start, int length, int num, int fujia)
{
for(int i = 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(int x = 0; x fujia; x++)
{
sum[index_sum] += data[a[x]];
}
index_sum++;
return;
}
}
}
int unique(int sum[], int length)
{
int temp = index_sum;
// printf(“temp:%d “,temp);
for(int i = 0 ; i length – 1; i++)
{
for(int j = i + 1; j length; j++)
{
if(sum[i] == sum[j])
{
/*若有相同的數字則減1,並退出此次循環*/
temp–;
break;
}
}
}
return temp;
}
C語言中的砝碼稱重問題
1、以f(k):幾種砝碼組合能稱出k的重量為狀態DP全部n個砝碼，然後枚舉去掉的m個砝碼的組合，對每種組合再DP一次，從f中減掉，剩下的就是能稱出的不同重量，複雜度O(n * C(n, m) * m * max(a))≤38760000。
2、例程：
#includestdio.h
#includestdlib.h
#includestring.h
#includememory.h
/*a數組用於存儲從n個整型數
* 據中取k個數字的數組下標值
* */
int a[100]={0};
/*data數組用於存儲實際的數據,也就是所有砝碼的
* 重量
* */
int data[4]={2,2,3,3};
/*sum數組用於保存再data中取k個樹的和,注意
* 沒有唯一化處理,也就是說可能裏面存在重複
* 唯一化處理使用函數unique;
* */
int sum[100] = {0};
/*index_sum用於記錄sum中最後一個數據的索引值
* */
int index_sum = 0;
/*這是一個遞歸實現,用於獲取從[start,length-num]的
* 某一位數,這個位數對應了data數組的下標,num是從
* data中取幾位數的,fujia是一個附加參數,用於記錄當
* 前獲取了幾位樹,從而方便操作數組a
* */
void GetNumberNew(int start, int length, int num, int fujia);
/*統計長度為length的sum數組中不重複元素的個數
* */
int unique(int[], int length);
int main()
{
//data數組長度
int length = 4;
for(int y = 1; y = length; y++)
{
/*從[0,num]中獲取y個數*/
GetNumberNew(0, length, y, y);
}
printf(“%d”,unique(sum, index_sum));
return 0;
}
void GetNumberNew(int start, int length, int num, int fujia)
{
for(int i = 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(int x = 0; x fujia; x++)
{
sum[index_sum] += data[a[x]];
}
index_sum++;
return;
}
}
}
int unique(int sum[], int length)
{
int temp = index_sum;
// printf(“temp:%d “,temp);
for(int i = 0 ; i length – 1; i++)
{
for(int j = i + 1; j length; j++)
{
if(sum[i] == sum[j])
{
/*若有相同的數字則減1,並退出此次循環*/
temp–;
break;
}
}
}
return temp;
}
原創文章，作者：OEZC，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/141134.html
微信掃一掃 
支付寶掃一掃 