Bin Packing using Dynamic Programming

Question

Problem Statement: 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.

My Solution:

Bin(C,N1,N2,N3) = max{Bin(C-N1,N1-1,N2,N3)+N1 if N1<=C and N1>0,
                      Bin(C-N2,N1,N2-1,N3)+N2 if N2<=C and N2>0,
                      Bin(C-N3,N1,N2,N3-1)+N3 if N3<=C and N3>0,
                      0 otherwise}

The above solution only fills a single bin efficiently. Can anybody suggest how to modify the above relation so that I get the total bins used for packing items efficiently?

possible duplicate of Bin Packing Dynamic Programming Question — Saeed Amiri
@SaeedAmiri In that question, they ask for the solution and here I am giving my own solution and asking for its correctness and modification. The solution I gave here is not given my anybody there. So will we still call it a duplicate? — Gaurav
This is your statement in the question: "The above solution only fills a single bin efficiently. Can anybody suggest how to modify the above relation so that I get the total bins used for packing items efficiently?" So you know it doesn't work, and you looking for the solution, Also your current solution is not DP, so you can't expect to change it a little to gain a DP solution (as stated in your Question title), So you need totally new way, and I think by this evidences, your question is duplicate. — Saeed Amiri
But for learning DP, This is helpful: cs.nyu.edu/~yap/classes/funAlgo/05f/lect/l7.pdf and may be my slide on restricted bin-packing: authorstream.com/Presentation/… — Saeed Amiri

WZL WZL · Accepted Answer · 2016-06-17T14:33:29

Problem You have n1 items of size s1 and n2 items of size s2. You must pack all of these items into bins, each of capacity C, such that the total number of bins used is minimised. Design a polynomial time algorithm for such packaging.

Here is my solution to this problem, and it's very similar to what you're asking.

DP method Suppose Bin(i, j) gives the min total number of bins used, then Bin(i, j) = min{Bin(i′, j′) + Bin(i − i′,j − j′)} where i + j > i′ + j′ > 0. There will be n^2 − 2 different (i′,j′) combinations and one pair of (n1,n2) combination. So the complexity is about O(n^2).

Complexity O(n^2)

Example: Let s1 = 3, n1 = 2, s2 = 2, n2 = 2, C = 4. Find the min bins needed, i.e., b.

<pre>
i j b
- - -
0 1 1
0 2 2
1 0 1
1 1 1
1 2 2
2 0 2
2 1 3
2 2 3  -> (n1,n2) pair
</pre>

So as you can see, 3 bins are needed.

<pre>
Note that Bin(2,2) = min{
  Bin(2,1) + Bin(0,1), 
  Bin(2,0) + Bin(0,2),
  Bin(1,2) + Bin(1,0),
  Bin(1,1) + Bin(1,1)} 
= min{3, 4} 
= 3
</pre>

Bin Packing using Dynamic Programming

1 Answers