本文目录一览：
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;
}
