其实，这是一篇试水文…


PART I - 前言

上次的代码有BUG，这次的代码合理不会有BUG（除非溢出）。 这道题竟然出现在校内OJ平台上的提前练手区域（1300 Problem）！简直过分！自我感觉这已经达到了ACM新手入门水平的题目了_(:з)∠)_ 所以因为这道题，原本要发的SZU OJ题组1、2就留到下一次吧 ╮(￣▽￣”)╭ 那天同级的高大佬和我讨论思路，根据他提供的思路我写出这次的代码，谢谢高大佬！


PART II - 题目


PART III - 思路

①排序

题目要求“将尽可能多的集装箱装上轮船”，即按集装箱的重量从小到大装入轮船内。因此，可先进行重量升序排序。

②贪心

开始按从轻到重的顺序填轮船，因为已经排序，所以是按数组从[0]开始填轮船，装到不能再装后，记录装载个数。

③ 穷举

以上面的图为例，可知输出结果的最大字典序为111110000000000（即排在前面的都被装载），最小字典序为000000000011111（即排在最后面的都被装载）。 将他们看作二进制数，那么将最大字典序设为起点，判定是否满足刚好存在5个’1’，’1’对应的集装箱重量之和是否不超过轮船可承载总重量。如果是，那么当前组合满足条件，输出结果；如果不是，则减1（因为减1能满足次最大字典序的要求），再次循环，直到满足条件为止。

由于无法直接使用二进制数计算，因此先将最大/最小字典序转换为十进制数（即31744和31），进行计算时转化为模拟二进制数字符数组，再进行上述操作。（当然也可以写一个类或者功能模拟二进制数运算）


PART IV - 源代码

//最优装载问题（贪心 + 穷举）
#include "iostream"
#include "cstdio"    //C++下写C代码，故用 cstdio
#include "algorithm"    //使用sort()函数
#include "malloc.h"    //动态分配数组内存
#include "cmath"     //使用pow()函数
void toBinary(char* array,int end, int nBox){    //十进制转二进制数组
    for(int n = nBox - 1; n >= 0; n--){
        array[n] = end%2 + '0';
        end /= 2;
    }
}

int main(){
    int weight;    //可承载重量
    int nBox;    //集装箱个数
    int maxNums = 0;    //按照从轻到重的顺序放置集装箱，可承载的最大数量
    scanf("%d%d", &nBox, &weight);
    int* arrayInput = (int*)malloc(nBox*sizeof(int));
    int* arrayInputUpper = (int*)malloc(nBox*sizeof(int));
    for(int n = 0; n < nBox; n++){
        scanf("%d", &arrayInput[n]);
        arrayInputUpper[n] = arrayInput[n];
    }


    std::sort(arrayInputUpper, arrayInputUpper + nBox);
    int temp = weight;
    for(int n = 0; n < nBox; n++){    //贪心，确定最大数量maxNums
        temp -= arrayInputUpper[n];
        if(temp >= 0){
            maxNums++;
        }else{
            break;
        }
    }

    int start = pow(2, maxNums) - 1;    //等比数列公式，下同
    int end = pow(2, nBox - maxNums)*(pow(2, maxNums) - 1);
    char* arrayRange = (char*)malloc(nBox*sizeof(char));
    for(;start <= end; end--){
        int times = 0;
        int temp = 0;
        toBinary(arrayRange, end, nBox);
        arrayRange[nBox] = '\0';
        for(int n = 0; n < nBox; n++){    //是否出现maxNums次1
            if(arrayRange[n] == '1'){
                times++;
            }
        }
        if(times != maxNums){
            continue;
        }

        for(int n = 0; n < nBox; n++){    //和是否不超过weight
            if(arrayRange[n] == '1'){
                temp += arrayInput[n];
            }
        }
        if(temp <= weight){
            break;     //满足结果跳出循环
        }else{
            continue;
        }
    }
    printf("%s", arrayRange);

    free(arrayInput);
    free(arrayInputUpper);
    free(arrayRange);
    return 0;
}