1、以f(k):几种砝码组合能称出k的重量为状态DP全部n个砝码，然后枚举去掉的m个砝码的组合，对每种组合再DP一次，从f中减掉，剩下的就是能称出的不同重量，复杂度O(n * C(n, m) * m * max(a))≤38760000。
2、例程：
#include<stdio.h>#include<stdlib.h>
#include<string.h>
#include<memory.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
}
#include<stdio.h>struct fama
{
int weightint 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=ki<ni++)
{
for(int j=0j<a[i].numj++)
{
p=1temp+=a[i].weight
for(int x=0x<mx++)
{
if(temp==w[x])
p=0
}
if(p) { w[m]=tempm++}
}
} return m}
void main()
{ int n=0
scanf("%d",&n)
for(int i=0i<ni++)
scanf("%d%d",&fama1[i].weight,&fama1[i].num)
int maxnum=0
for(i=0i<ni++)
maxnum+=count(fama1,i,n)
printf("%d\n",maxnum)
}
给分吧，速度
main( ){ int n1,n2,n3,n4,n5,n6
int n[5000]={0},i=0,j=0,totle=0,k=0
printf("KechengShi xian guo cheng \n\n")
for(n6=1n6>=-1n6--)
for(n5=1n5>=-1n5--)
for(n4=1n4>=-1n4--)
for(n3=1n3>=-1n3--) /*1代表砝码放在右盘，0代表该砝码没有用到，-1代表砝码放在左盘*/
for(n2=1n2>=-1n2--)
for(n1=1n1>=-1n1--)
{ n[k]=1*n1+2*n2+5*n3+10*n4+20*n5+50*n6
if(n[k]>0)
{ printf(" %d= %d*1+%d*2+%d*5+10*%d+20*%d+50*%d\n",n[k],n1,n2,n3,n4,n5,n6)
i++/*每20种称重方法打印一屏*/
k++
if (i>=20)
{getch()
i=0
clrscr()
printf("zhong liang cheng zhong fang fa\n")
}
}
}
getch()
clrscr()
for(i=0i<ki++)
for(j=i+1j<=kj++) /*消除重复项*/
{ if(n[i]==n[j])
n[j]=0
}
printf("ke yi cheng chu de zhong liang shu wei :\n\n")
for(i=0i<=ki++)
if(n[i]>0)
{
printf("%-5d",n[i]) /*输出称出的重量数和他们总共的个数*/
totle++
}
printf("\n\ngong %d zhong \n",totle)
getch()
}
