2
$\begingroup$

I solved a problem similar to the knapsack problem.

There are two packages with a capacity of $P$ on a production line. We want to put $N$ items in them with the weights $w_1,...w_n$ in a pre-defined order (the best order). We can put an item in the package 1 or the package 2 or close one package and replace it with a new package and put the item in it. What is the minimum number of packages?

Let $m(n,p1,p2)$ be the minimum number of packages for $n$ items where the capacity of package 1 is $p1$ and the capacity of the package 2 is $p2$.

I must keep track of the free capacity of each package which is not always $P$ (empty state)

let $w_n$ be the weight of the $n_{th}$ item.

It's my solution using dynamic programming:

def packaging(N, P1, P2, w):
    M = np.zeros((N+1, P1+1, P2+1))
    for n in range(N+1):
        for p1 in range(P1+1):
            for p2 in range(P2+1):
                wn = 0 if n == 0 else w[n-1]
                if n == 0:
                    M[n][p1][p2] = 0
                elif wn > p1 and wn > p2:
                    M[n][p1][p2] = M[n-1][p1][p2] + 1
                elif wn > p1:
                    M[n][p1][p2] = M[n-1][p1][p2-wn]
                elif wn > p2:
                    M[n][p1][p2] = M[n-1][p1-wn][p2]
                else:
                    M[n][p1][p2] = min(M[n-1][p1-wn][p2], M[n - 1][p1][p2 - wn])
    return M[N][P1][P2]

Its order is $O(NP^2)$. There is an $O(NP)$ solution for it. How can I enhance my solution to reach it?

Further updates might come to reformat the solution in a mathematical notation.

Source: Tehran University, Fall 2018, Advanced algorithms practice

$\endgroup$
  • $\begingroup$ The problem that you state is NP-complete even if the sum of the weights is just equal to 2P (so you need 2 or 3 packages). So you are not going to get an optimal solution in polynomial time. Are you trying some greedy algorithm for approximation? In that case I don't have a clue what P1 and P2 are supposed to mean. $\endgroup$ – gnasher729 Oct 27 '18 at 17:28
  • $\begingroup$ @Apass.Jack I did, sorry, tonight is due date and didn't have time to make it better. $\endgroup$ – Ahmad Oct 27 '18 at 17:32
  • $\begingroup$ @gnasher729 it could be NP in respect to $N$, but can have $O(NP)$ time. $\endgroup$ – Ahmad Oct 27 '18 at 17:32
  • $\begingroup$ What I said is the way to make it faster especially when time is tight. Or just do not include your code, which asks people to read it before posting an answer, which slow down the coming of an answer very much. $\endgroup$ – Apass.Jack Oct 27 '18 at 17:33
  • 1
    $\begingroup$ I am still thinking ... I believe I am approaching the essence of the problem ... $\endgroup$ – Apass.Jack Oct 27 '18 at 18:01
1
$\begingroup$

A very nice question.

Here is the brief idea of a more efficient algorithm. The central idea is how to fill one package and close it with minimal unfilled capacity left. That is a standard knapsack problem that can done efficiently with dynamic programming.

However, now we have two packages available, each might have different initial capacities available, as you have pointed out.

What to do? Then do two knapsack problems at the same time!

Right after you have closed one package, you have two packages, one with $a_1$ available capacity and the other with $a_2$ available capacity. We have two knapsack problems here: how to fill the one with $a_1$ capacity as much as possible without bursting the other one and how to fill the one with $a_2$ capacity as much as possible without bursting the other one. Solve them separately. Compare the result to find which one get less free capacity left. Choose that package and its maximal filling found just now and close it. Fill the other one with the items that should have been used before closing the previous one. Repeat the process.

(Further update might come to clarify the above explanation. But this should get you going.)

$\endgroup$
  • $\begingroup$ If the process repeats for all items, then isn't it $O(N^2P)$? $\endgroup$ – Ahmad Oct 27 '18 at 23:22
  • $\begingroup$ For every two knapsack problems we solve together, it can only use at most the next items the sum of whose weights is not greater than $a_1+a_2$. Find those items and solve the two knapsack problems using those items only. Were you using all of the remaining items? That would slow down the algorithm. $\endgroup$ – Apass.Jack Oct 28 '18 at 0:59
  • $\begingroup$ So the proposed algorithm is a nested algorithm with the outer one being a greedy procedure and the inner one being two runs of a procedure by dynamic programming. $\endgroup$ – Apass.Jack Oct 28 '18 at 1:05
0
$\begingroup$

Thanks to whoever came up with the problem. Very nice problem. It is NP-complete even for the trivial case where the sum of weights equals 2P, because then it is equivalent into splitting a set of n weights into two subsets of equal weight, which is NP complete. It's different from bin packing, because one package must be closed when weights with a total of 2P have been processed. Interesting problem.

Your problem asked for ONE package size P. The same for all packages. Somehow you changed that to two package sizes. That explains why you need N*P1*P2 steps instead of N*P. I still have no idea what you are trying to do.

Have you actually tried your algorithm with real numbers and got any success? If all wi = 1, P1 = P2 = P, n = 2P + k, then the solution is k. For example, 100 items of size 1, packed into packages of size 10, your solution says it needs 80 packages.

I suspect that you were asked to produce a greedy algorithm which will produce not the optimal solution, but a near optimal solution. I am saying that because an optimal solution is difficult and will take exponential time.

$\endgroup$
  • $\begingroup$ I must keep track of the free capacity of each package which is not always $P$ (empty state) $\endgroup$ – Ahmad Oct 27 '18 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.