GESP4级考试语法知识（贪心算法（五））

装箱问题1代码：

#include <iostream>
using namespace std;
int main()
{
    int a,b,c,d,e,f;
    while (true)
	{
        int N = 0;        // 计算需要的包裹数
        cin>>a>>b>>c>>d>>e>>f;
        if (a==0&&b==0&&c==0&&d==0&&e==0&&f==0)
            break;
        N = f+e+d+(c+3)/4;// 从6开始，计算最少需要的箱子数
        int y=5*d;        // y:计算可存放2*2货物的空隙个数
        if (c%4==1) y+=5;
        else if (c%4==2) y+=3;
        else if (c%4==3) y+=1;
        if (b>y)          // 如果2*2预留位不够再加包裹
		{                 
            N += (b-y+8)/9;
        }
        int x = 36*N-36*f-25*e-16*d-9*c-4*b;// x计算可存放1*1箱子的个数
        if (a>x)
		{
            N += (a-x+35)/36;
        }
        cout<<N<<endl;
    }
}

装箱问题2代码：

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