完美的装箱解决方案算法

Question

有没有一种方法可以完全有效地解决1D垃圾箱包装，而不是暴力？如果不是，用暴力解决问题的最佳方法是什么？我试过减少最佳拟合和减少首次拟合，但它们都不完全有效。到目前为止，我所做的代码如下：（有些功能没有显示，即排序和交换，但假设这些功能完美地工作，它们确实工作！）

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
void swap(int* x, int* y);
void sort(int values[], int n);
int choose(int fill[], int *fills, int val, int max);
int main(void){
    int lw, cn;
    //  get first two numbers
    scanf("%i", &lw);
    scanf("%i", &cn);   
    //
    int cw[cn], i, lf[1000], lc = 0, lp;
    memset(lf, 0 , sizeof(lf));
    //  get width of all the clothes
    for(i = 0; i < cn; i++){
        scanf("%i", &cw[i]);
    }
    //  sort cw 
    sort(cw, cn);
    //  apply bin packing - bestfit, sorted
    for( i = 0; i < cn; i++){
        lp = choose(lf, &lc, cw[i], lw);
        lf[lp] += cw[i];
        printf("lf[%i] += %i, maakt %i n", lp , cw[i], lf[lp]);
    }
    //  return nr of bins
    printf("Uiteindelijke lc= %in", lc);
}

int choose(int fill[], int *fills, int val, int max){
    int x, lessid, less = 0;
    bool changed = 0;
    for(x = 0; x <= *fills; x++){
    /* best fit
    if( ((fill[x] + val) < max) && ((fill[x] + val) > less)){
            lessid = x;
            less = fill[x];
            changed = 1;
        }
        if (changed == 1) { return lessid;}
        else {
            *fills+=1;
            return *fills;
        }
    }*/
    //First fit
    if( (fill[x] + val) < max) {
            return x;
    }
    *fills+=1;
    return *fills;
    }
}

Answer 1

分支和绑定比强力更有效。但它仍然是一个详尽的搜索，而且它仍然遇到了可扩展性的障碍。