Bin Packing Dynamic Programming Question

You have n1 items of size s1, n2 items of size s2开发者_如何转开发, and n3 items of size s3. You'd like to pack all of these items into bins each of capacity C, such that the total number of bins used is minimized.

How can we achieve a solution using minimum number of bins? Greedy isn't surely working.

It is not a dumb question, IMO.

Bin packing in general is known to be NP-Complete.

But your case, Bin packing with fixed number of object weights is an interesting variant.

The following paper claims to have a polynomial time algorithm which comes withing 1 of optimal: http://linkinghub.elsevier.com/retrieve/pii/S0377221706004310 when you allow 3 different sizes. (Caveat: I am only going by the abstract).

So I am guessing this version is NP-Hard too and Greedy algorithm will likely not work. Not so sure of dynamic programming (bin packing is strongly NP-Complete).

Hope that helps.

It won't be efficient, but you can solve this with a straightforward dynamic programming (DP) algorithm. If you have a fixed number of sizes, it will be polynomial in the inputs with the degree of the polynomial depending on the number of difference sizes that you have.

I have included an implementation that for 3 different sizes will be O(n1 * n2 * n3 * (C/s2) * (C/s3) * ((n1s1 + n2s2 + n3*s3)/C)) with a pretty crappy constant. (That figure comes courtesy of the fact that we the number of distinct patterns of availability is O(n1 * n2 * n3) and for each one we generate O((C/s2) * (C/s3)) possible next bins to try, for each of which we have to work with a set of bins whose size is O((n1*s1 + n2*s2 + n3*s3)/C)). A number of routine optimizations could massively speed up this program.)

#!/usr/bin/env python3 -B -u
#-*- coding: utf-8 -*-

import sys
import heapq

def min_bins(bin_size, sizes, counts):
    available = zip(sizes, counts)
    available.sort(reverse=True)
    seen = set([])
    upcoming = [(0, available, [])]
    while 0 < len(upcoming):
        (n, available, bins) = heapq.heappop(upcoming)
        for (bin, left) in bin_packing_and_left(bin_size, available):
            new_bins = bins+[bin]
            if 0 == len(left): return new_bins
            elif left not in seen:
                heapq.heappush(upcoming, (n+1, left, new_bins))
                seen.add(left)

def bin_packing_and_left(bin_size, available, top=True):
    if 0 == len(available): yield ((), ())
    else:
        (size, count) = available[0]
        available = available[1:]
        for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
            can_use = (bin_size-used)/size
            if count <= can_use:
                yield(((size, count), )+bin, left)
            elif 0 < can_use:
                yield(((size, can_use), )+bin, ((size, count-can_use), )+left)
            else: yield(bin, ((size, count), )+left)

def bin_packing_and_left_size(bin_size, available):
    if 0 == len(available): yield ((), (), 0)
    else:
        (size, count) = available[0]
        available = available[1:]
        for (bin, left, used) in bin_packing_and_left_size(bin_size, available):
            for i in range(1+min(count, (bin_size-used)/size)):
                if count == i:
                    yield(((size, count), )+bin, left, used+size*count)
                elif 0 < i:
                    yield(((size, i), )+bin, ((size, count-i), )+left, used+size*i)
                else: yield(bin, ((size, count), )+left, used)

if __name__ == "__main__":
    answer = min_bins(23, (2, 3, 5), (20, 30, 40))
    print(len(answer), answer)

It can be done in O(n1*n2*n3)...

Lets say, f(i,j,k) is the minimum no. of bins that are required to fit i , j and k items of size s1, s2, s3 respectively..

Note: C is the capacity of the bin

f(i,j,k) will hold 2 kinds of information:

a) (The min no. of bins that are currently required) - 1. Say the property is B1.

b) The current size of the last bin which is available for further filing.. Say the property is B2 .. where 0 < B2 <= C

Hence, the recurrence would be :

f(i,j,k)([B1],[B2]) =
  min 
 { 
    f(i-1, j, k)( [B1] + [B2 + S1]/(C+1) , [B2 + S1] <=C ? [B2 + S1] : [B2 + S1 - C]) ,
    f(i, j-1, k)( [B1] + [B2 + S2]/(C+1) , [B2 + S2] <=C ? [B2 + S2] : [B2 + S2 - C]) ,
    f(i, j, k-1)( [B1] + [B2 + S3]/(C+1) , [B2 + S3] <=C ? [B2 + S3] : [B2 + S3 - C])
 }

The minimum no. of bins required : 1 + f(n1, n2, n3)[B1]

If you can reduce your problem to a 1d bin-packing you want to use a greedy algorithm used here: http://www.developerfusion.com/article/5540/bin-packing

If size is unidimensional, or if it can be reduced to an unidimensional value, you can solve this as a multi-sack knapsack problem (MKP), where the weight of a item is equal to its benefit. If you set #bin to the upper-bound for the number of items available (in a glance, if your instance is not very very high, this value can be #items), you can solve this problem optimally with a branch and bound or other optimization algorithm. If you can admit a non-optimal solution, there is some feasible greedy algorithms.

However, I'm not so sure since I've never studied this problem deeply. Nevertheless, there is a book called "Knapsack Problems" that presents formulations and algorithms, including to bin packing problems. Not hard to find it as a PDF in the Internet.

Hope this help. Good luck.

The minimum number of bins assuming excellent packing would be B = ceiling( sum(n(i)*s(i) for i in 1..3) / C )

Use what is called first_fit, but is actually worst_fit, with swapping, from here to see if the items fit into the B bins. If not, increment B and repeat until they fit.

Here's a sketch of the DP algorithm for this one.

Recursive Relation: We recurse on B(i, j, k), the minimum number of bins of capacity C required to pack i items of size s1, j items of size s2 and k items of size s3. The relation is:

B(i, j, k) = min {B (x,y,z) , B(i-x, j-y, k-z)} 
where 0<=x<=i; 
0<=y<=j; 
0<=z<=k

where at least one of x,y or z must be greater than 0 and one of x,y or z must be less than i, j or k respectively.

Running Time: B is size O(n3) and computing each element of B requires time O(n3) for a total time of O(n6).

If we can find the optimum solution to one bin, that means maximum number of elements I can fit in one bin,this would lead to answer.

Let us assume a elements of size S1,b elements of size S2,c elements of size S3 are the maximum number of elements that I can fit in one bin. So maximum size that I can fit in one bin is K=a*S1+b*S2+c*S3.so the answer would be (n1*S1+n2*s2+n3*s3)/K + (n1*S1+n2*s2+n3*s3)%K no of bins.

Finding K is easier than standard Knapsack problem.If I assume that all the optimal values till i exists 1<=i<=C.Then optimal value of i+1 can be written recursively as

M(i+1) = max(M(i),M(i-S1)+S1,M(i-S2)+S2,M(i-S3)+S3).

This function is one of the most optimal sub-functions

1. first-fit
2. best-fit
3. worst-fit

etc.

function ElementFit(weight, c) {
  let sum = 0,
    p = 1,
    temp = 0,
    index = 0;
  let str = "";
  let bin_index = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
  let bin_sum = [0, 0, 0, 0, 0, 0, 0];
  // Place items one by one
  for (let i = 0; i < weight.length; i++) {
    bin_sum = [0, 0, 0, 0, 0, 0, 0];
    for (let k = 0; k < p; k++)
      for (let j = 0; j <= i; j++) {
        if (bin_index[j] == k + 1) bin_sum[k] += weight[j];
      }
    for (let a = 0; a < p; a++) {
      if (bin_sum[a] + weight[i] <= c) {
        bin_index[i] = a + 1;
        break;
      } else if (a == p - 1) {
        p += 1;
        bin_index[i] = p;
        break;
      }
    }
    if (p > 1) {
      temp = weight[i];
      index = i;
      for (let k = 1; k < p; k++)
        for (let j = 0; j < i; j++)
          if (bin_index[j] == k)
            if (temp > weight[j])
              if (bin_sum[k - 1] - weight[j] + temp <= c) {
                bin_index[index] = k;
                bin_index[j] = p;
                bin_sum[k - 1] = bin_sum[k - 1] - weight[j] + temp;
                temp = weight[j];
                index = j;
              }
    }
  }
  for (let k = 0; k < p; k++)
    for (let j = 0; j < weight.length; j++) {
      if (bin_index[j] == k + 1) bin_sum[k] += weight[j];
    }
  for (let k = 1; k <= p; k++) {
    let number = bin_sum.indexOf(Math.max(...bin_sum));
    for (let i = 0; i < weight.length; i++)
      if (bin_index[i] == number + 1) {
        str = str + weight[i].toString();
        str += ",";
      }
    bin_sum[number] = 0;
  }
  return str;
}
let weight = [900, 900, 1000, 100, 50, 32, 30, 15];
let c = 1045;
console.log(ElementFit(weight, c));