4 ms·
Can somebody tell me if the following problem is solvable using knapsack (so far I've been only able to come up with bruteforce solution with some optimizations
by itomatik 13y ago
Can somebody tell me if the following problem is solvable using knapsack (so far I've been only able to come up with bruteforce solution with some optimizations):
We have different product types and for each product know it's amount. Let's say we have 20 different product types. For each type we know how much we've got (i.e. 10k of product type 1, 15k of product type 2, etc.)
Now we want to put those products into different bags. Each bag must have 5 products.
A particular combination of products inside of the bag is considered a "bag type". If we choose a particular "bag type" we must to have at least 7,500 units of such bag type.
For each bag type we have a certain cost function.
Now the problem is to find bags types and corresponding amounts such that total cost is maximized.
- danielovich 13y agoKnapsack! And there is no way to determine the best solution before every combinations has been tried. I have been in the exact same spot as you but ended up making a specific module for it which didn't needed any computation beforehand.
- itomatik 13y agoHold on, so you did you bruteforce all-all possible solutions and then just picked the best one out of them? How many products you had? Was it close to what I have? In my case there are just too many possible solution. I waited for an hour on my current one and it didn't finish :) What was your strategy with regards of how much each bag type you select? Try all possible from current_max downto 7,500?
- itomatik 13y agoIn which context were you solving this problem? I'm trying to optimize products distribution.