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?
How to use the 0-1 knapsack problem with more than one bag
algorithms
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.