1

The 0-1 knapsack is a well-known algorithm that solves the problem of finding the maximum profit P of putting some of n object( each of weight w and profit p) in a bag of capacity W.

How can I use the same algorithm to find the maximum profit of putting sum of the n elements in more than one bag?

I'm trying to solve this ACM problem. I'm thinking that I can think of it as an extended 0-1 knapsack problem, where the number of the group is the weight of the items w, ant their money is the item's profit 'p'. I'm also thinking that there're more than one bag to fill, each with maximum weight Wi.

My question is, what is the optimal way for optimizing the 0-1 knapsack problem to solve a case where there's more than one bag?

2 Answers 2

0

To tackle this problem I would follow a different approach:

A table can only be used once and only people from the same group can sit at it. What you want to do is sort all your groups of guests by decreasing amount that they will spend in the restaurant, and then allocate them to the smallest table that can accommodate them, or move to the next group if no available table are big enough to accommodate them.

1
  • I thought at first that greedy solutions wont work because the sum of two small numbers may become bigger than a number bigger than them both, but I realized that this won't happen here. If any one wants the code of my solution for this problem, you can found it here. Thanks for your help.
    – Abozanona
    Jul 5, 2016 at 14:36
0

It's a much simpler problem because one group will take one table.

Take the smallest table, seat the most valuable group that fits. Take the second table and again seat the most valuable group that fits. And so on.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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