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.