CODEWITHSUNDEEP
algorithmbin-packing
Gaurav
Gaurav

Reputation: 1045

Bin Packing using Dynamic Programming

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?

Upvotes: 1

Views: 3635

Answers (1)

WZL
WZL

Reputation: 21

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>

Upvotes: 1

Related Questions