正文
装箱问题c语言函数,装箱问题c语言函数表
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
c语言1000发子弹装箱问题,如何编写该程序
你可以用一个循环来给数组赋值,因为用的是手机,打字不好打,我就写一下循环部分了吧,,,
for(i=2;i=10;i
)
for(j=1;j=i-1;j
)
a[i]=a[i]*2;,,注意数组我这里是11个元素,第一个元素没用,后面刚好十个方便应用。然后数组一开始要初始化全为1
C语言的``装箱问题
我运行没问题。
#define N 100
main()
{
int sum, set, i, j, max, check[100];
int volume[N]={8,3,12,7,9,7}, n=6,_n, v=24;
/*scanf("%d", v);
scanf("%d", n);
for (i=1;i=n;i++)
scanf("%d", volume[i]);
max=0;
*/
set=1;
for (i=1;i=n;i++)
set*=2; //计算2的N次方。
for (i=0;i=set;i++)
{
for (j=1;j=n;j++)
check[j]=0; //清空数组
j=i;
sum=1;
while (j=1) //把数据转换成二进制数制(1代表取,0代表不取)
{
check[sum]=j%2;
j/=2;
sum++;
}
sum=0; //计算该方案占用的体积
for (j=1;j=n;j++)
if (check[j]==1)
sum+=volume[j];
if ((sum=v)(sum=max)) //根据题意作比较
max=sum;
}
printf("%d",v-max); //输出剩余体积。
system("pause");
}
我确实运行没问题。OK,0
装箱问题
有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30,每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
样例
输入:
24 一个整数,表示箱子容量
6 一个整数,表示有n个物品
8 接下来n行,分别表示这n 个物品的各自体积
3
12
7
9
7
输出:0 一个整数,表示箱子剩余空间。
# include stdio.h
# include stdlib.h
typedef struct ele
{ int vno;
struct ele *link;
} ELE;
typedef struct hnode
{ int remainder;
ELE *head;
struct hnode *next;
} HNODE;
void main()
{
int n, i, box_count, box_volume, *a;
HNODE *box_h, *box_t, *j;
ELE *p, *q;
printf("输入箱子容积\n");
scanf("%d",box_volume);
printf("输入物品种数\n");
scanf("%d",n);
a=(int *)malloc(sizeof(int)*n);
printf("请按体积从大到小顺序输入各物品的体积:");
for (i=0;in;i++) scanf("%d",a+i);
box_h=box_t=NULL;
box_count=0;
for (i=0;in;i++)
{ p=(ELE *)malloc(sizeof(ELE));
p-vno=i;
for (j=box_h;j!=NULL;j=j-next)
if (j-remainder=a[i]) break;
if (j==NULL)
{ j=(HNODE *)malloc(sizeof(HNODE));
j-remainder=box_volume-a[i];
j-head=NULL;
if (box_h==NULL) box_h=box_t=j;
else box_t=box_t-next=j;
j-next=NULL;
box_count++;
}
else j-remainder-=a[i];
for (q=j-head ;q!=NULLq-link!=NULL;q=q-link);
/*q=j-next;q!=NULLq-link!=NULL;q=q-link*/
if (q==NULL)
{ p-link=j-head;
j-head=p;
}
else
{ p-link=NULL;
q-link=p;
}
}
printf("共使用了%d只箱子",box_count);
printf("各箱子装物品情况如下:");
for (j=box_h,i=1;j!=NULL;j=j-next,i++)
{ printf("第%2d只箱子,还剩余容积%4d,所装物品有;\n",i,j-remainder);
for (p=j-head;p!=NULL;p=p-link)
printf("%4d",p-vno+1);
printf("\n");
}
}
C语言 动态规划 完全装箱问题
【问题】 装箱问题
问题描述:装箱问题可简述如下:设有编号为0、1、…、n-1的n种物品,体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于0≤i<n,有0<vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。
若考察将n种物品的集合分划成n个或小于n个物品的所有子集,最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时间是无法承受的。为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的体积从大到小排序,然后按排序结果对物品重新编号即可。装箱算法简单描述如下:
{ 输入箱子的容积;
输入物品种数n;
按体积从大到小顺序,输入各物品的体积;
预置已用箱子链为空;
预置已用箱子计数器box_count为0;
for (i=0;i { 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j;
if (已用箱子都不能再放物品i)
{ 另用一个箱子,并将物品i放入该箱子;
box_count++;
}
else
将物品i放入箱子j;
}
}
上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为:60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。
若每只箱子所装物品用链表来表示,链表首结点指针存于一个结构中,结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。
【程序】
# include
# include
typedef struct ele
{ int vno;
struct ele *link;
} ELE;
typedef struct hnode
{ int remainder;
ELE *head;
Struct hnode *next;
} HNODE;
void main()
{ int n, i, box_count, box_volume, *a;
HNODE *box_h, *box_t, *j;
ELE *p, *q;
Printf(“输入箱子容积\n”);
Scanf(“%d”,box_volume);
Printf(“输入物品种数\n”);
Scanf(“%d”,n);
A=(int *)malloc(sizeof(int)*n);
Printf(“请按体积从大到小顺序输入各物品的体积:”);
For (i=0;i Box_h=box_t=NULL;
Box_count=0;
For (i=0;i { p=(ELE *)malloc(sizeof(ELE));
p-vno=i;
for (j=box_h;j!=NULL;j=j-next)
if (j-remainder=a[i]) break;
if (j==NULL)
{ j=(HNODE *)malloc(sizeof(HNODE));
j-remainder=box_volume-a[i];
j-head=NULL;
if (box_h==NULL) box_h=box_t=j;
else box_t=boix_t-next=j;
j-next=NULL;
box_count++;
}
else j-remainder-=a[i];
for (q=j-next;q!=NULLq-link!=NULL;q=q-link);
if (q==NULL)
{ p-link=j-head;
j-head=p;
}
else
{ p-link=NULL;
q-link=p;
}
}
printf(“共使用了%d只箱子”,box_count);
printf(“各箱子装物品情况如下:”);
for (j=box_h,i=1;j!=NULL;j=j-next,i++)
{ printf(“第%2d只箱子,还剩余容积%4d,所装物品有;\n”,I,j-remainder);
for (p=j-head;p!=NULL;p=p-link)
printf(“%4d”,p-vno+1);
printf(“\n”);
}
}
c语言装载问题 急!请在这个基础上修改
#include stdio.h
#include stdlib.h
int c1, c2, n, w[10]; int weight = 0, max = 0;
int count1 = 0, count2 = 0; //添加的代码
int sum = 0;
int arrC1[10], arrC2[10];//用来装C1 C2货船上的货物的重量
void search(int m)
{
if (m == n)
{
if (weight = c1)
if (weight = max)
max = weight;
}
else
{
weight += w[m];
search(m + 1);
//添加的代码 如果max已被赋值,则c1货船装到了最大重量的货物 函数立即return不再继续执行,
//把返回路径上添加的重量放到c1的数组里
if (max0 c1=weight sum-weight=c2 )
{
arrC1[count1] = w[m]; count1++; return;
}
weight -= w[m];
search(m + 1);
//添加的代码 如果max已被赋值,则c1货船装到了最大重量的货物 函数立即return不再继续执行,
//把剔除的货物放到c2的数组里
if (max 0 /* c1 = weight*/ sum - weight = c2)
{
arrC2[count2] = w[m]; count2++; return;
}
}
}
int main()
{
int i;
scanf("%d%d%d", c1, c2, n);
while (n != 0)
{
for (i = 0; i n; i++)
{
scanf("%d", w[i]); sum += w[i];
}
search(0);
if (sum - max = c2)
{
printf("Yes\n");
//添加的代码 输出c1货船上的货物
printf("c1: ");
for (int i = 0; i count1; i++)
printf(" %d ", arrC1[i]);
//输出c2货船上的货物
printf("\tc2: ");
for (int i = 0; i count2; i++)
printf(" %d ", arrC2[i]);
printf("\n");
}
else
printf("No\n");
max = 0;
sum = 0;
//添加的代码
count1 = 0;
count2 = 0;
//刚才忘了把weight清0 所以出错了
weight = 0;
scanf("%d%d%d", c1, c2, n);
}
return 0;
}
【急】C语言的箱问题
这是动态规划问题的典型问题
你可以搜一下动态规划解决“装箱问题”和“背包问题”,看一下思想就明白了。
祝顺利解决。
【2001年普及组4】装箱问题
Time Limit:1000MS Memory Limit:65536K
Total Submit:512 Accepted:251
Description
有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30),每个物品有一个体积 (正整数)。要求从m个物品中,任取若千个装入箱内,使箱子的剩余空间为最小。
[样例]
输入:
24 一个整数,表示箱子容量
6 一个整数,表示有n个物品
8 接下来n行,分别表示这n个物品的各自体积。
3
12
7
9
7
输出:
0 一个整数,表示箱子剩余空间。
Input
第一行为箱子容量为v;第二行为物品数;以下n行分别为每个物品的体积;
Output
箱子剩余空间
Sample Input
24
6
8
3
12
7
9
7
Sample Output
*/
/*
动态规划,设:a[i,j] 表示选前i个物品刚好能装满 j 空间,则有:
a[i,j] = a[i-1][j] or a[i-1][j-v[i]] jv[i]
a[i,0] = 0 ;
不过,这题有点特殊:
就是:
a[i,j]只与: i-1有关
所以可以降到一维...
*/
#include stdio.h
#include string.h
#define MAX 20001
int main(void)
{
int m,n,tv,v,i,j,k ;
int a[MAX] ={0} ;
a[0] = 1;
scanf("%d",v) ;
scanf("%d",n) ;
for(i=1 ; i= n ; i++)
{
scanf("%d",tv);
for(j=v ; j=tv ; j--)
if(!a[j])
a[j] = a[j-tv] ;
}
m = v ;
while ( a[m] == 0)
m -- ;
printf("%d ",v-m) ;
return 0 ;
}