文章目录

前言一、题目二、算法思想三、代码

前言

请勿直接复制黏贴代码，算法思想是关键。

一、题目

二、算法思想

刚开始研究这道题的时候，没搞懂大致的题意，之后终于想通了。 这题给了我们N个物品、N个默认大小为100的箱子和N个物品对应的大小。 如果我们把一个大小为60的物品，放入了序号为1的箱子中，那这个1号箱子还剩下40的空间能装其他的物品。 这道题的贪心思想，就是寻求最大的空间利用率，即最小的箱子使用数。

针对之后需要输出物品的大小和所在箱子序号的情况，这个时候可以利用结构体数组，或者你使用两个数组来存储对应的关系也行。 结构体数组的序号可以初始化，也可以不初始化，因为之后仍需要对每一个物品进行所在箱子序号的判断。

除了物品对应的结构体数组外，还需要定义物品数/箱子数N、箱子剩余量的数组box、放置物品所用的箱子数num 初始化箱子的容量你可以和我一样用循环，也可以使用int box[1000]={100}在定义的时候就进行初始化。

然后可以使用双重循环，外循环是对物品结构体数组的遍历，内循环是对箱子数组遍历。 每当当前的箱子容量大于等于当前物品的大小时，就用一个变量index_box变量记录这个箱子的编号， 并扣除对应箱子的容量，再break出来避免之后不必要的遍历。 在每一次的箱子遍历结束后，就将找到的箱子编号存到物品信息当中。

之后就是输出所有箱子的大小和对应的箱子编号。 在计算箱子使用的数量时，只需要遍历box数组，找到其中剩余容量不为100的箱子并统计数量即可。

三、代码

#include<iostream> using namespace std; struct th { int weight;//物品的重量 int index=0;//物品所在箱子序号，为0时表示未放入箱子 }thing[1000];//结构体数组 int main() { int N;//物品个数、箱子个数 int box[1000];//各个箱子的剩余容量 int num=0;//所需箱子的个数 int i,j; cin>>N; for(i=1;i<=N;i++) cin>>thing[i].weight; /* for(i=1;i<=N;i++) cout<<weight[i]<<" "; */ for(i=1;i<=N;i++)//初始化箱子容量 box[i]=100; for(i=1;i<=N;i++)//遍历所有的物品，找到对应的箱子 { int index_box;//用于存储找到的箱子序号 for(j=1;j<=N;j++)//遍历所有的箱子 { if(box[j]>=thing[i].weight)//当找到合适的箱子时 { index_box = j;//记录编号 box[j]-=thing[i].weight;//将物品放入箱子 break; } } thing[i].index=index_box;//标记该物品对应的箱子编号 } for(i=1;i<=N;i++)//显示所有物品及其箱子编号 cout<<thing[i].weight<<" "<<thing[i].index<<endl; for(i=1;i<=N;i++)//统计使用过的箱子数目 { if(box[i]!=100) num++; } cout<<num<<endl;//输出使用的箱子总数 return 0; }