Ⅰ 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;
}