实验7-1-13 装箱问题（20 分）
假设有N项物品，大小分别为s1、s2、…、si、…、sN，其中si为满足$1\le si\le 100$的整数。要把这些物品装入到容量为100的一批箱子（序号1-N）中。装箱方法是：对每项物品, 顺序扫描箱子，把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程，并输出每个物品所在的箱子序号，以及放置全部物品所需的箱子数目。
输入格式：
输入第一行给出物品个数$N（\le 1000）$；第二行给出N个正整数$si$（$1\le si \le 100$，表示第i项物品的大小）。
输出格式：
按照输入顺序输出每个物品的大小及其所在的箱子序号，每个物品占1行，最后一行输出所需的箱子数目。
输入样例：
1
2
| 8
60 70 80 90 30 40 10 20
|
输出样例：
1
2
3
4
5
6
7
8
9
| 60 1
70 2
80 3
90 4
30 1
40 5
10 1
20 2
5
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define TSIZE 45
int main()
{ int n,i,j,flag,max;
int s[1000];
int dun[1000];
int biao[1000];
while(scanf("%d",&n)!=EOF)
{ for(i=0;i<100;i++)
{
biao[i]=-1;
}
for(i=0;i<n;i++)
{
scanf("%d",&s[i]);
dun[i]=s[i];
}
biao[0]=0;
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
flag=0;
if(dun[i]+dun[j]<=100)
{
dun[j]=dun[j]+dun[i];
dun[i]=0;
biao[i]=j;
flag=1;
break;
}
}
if(flag==0)
{
biao[i]=i;
}
}
max=0;
for(i=0;i<n;i++)
{
if(biao[i]>max)
max=biao[i];
}
for(i=0;i<n;i++)
printf("%d %d\n",s[i],biao[i]+1);
printf("%d\n",max+1);
}
return 0;
}
|
