Perfect Bin Packing solution algorithm

Question

Is there a way to solve a 1D bin-packing totally efficient, differtent from brute-force? And if it isn't, what is the best way to brute-force attack the problem? I've tried decreasing best fit, and decreasing first fit, but they both don't work totally efficient. The code i've made untill now is below: (Some functions are not shown, namely Sort and Swap, but suppose these work perfectly, they do!)

#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= %i\n", 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

Branch and Bound is more efficient than Brute Force. But it's still an exhaustive search and it still hits the scalability wall.