I want to start off by saying that I don't know the solution to this. I wanted to start a discussion from others about what ideas they have to solve it. Also I couldn't find about this anywhere else on the internet so thats why I'm asking this here. Please don't be mad at me if its a bad question.
So there's the 0/1 knapsack problem where you maximize the profit. Thats cool but theres only one sack. What if theres more than one sack? Everything else is the same. A bunch of objects with some weight and profit, bags with some weight limit (all bags have same weight limit), and you can only, either take an object or leave it. You can't break it up into different bags or only take fractions of it or anything like that.
Any ideas are welcome.
The only approach I can think of is just try out all the permutations of the object list and insert them ony by one into the bags till they fill up then move on to the next bag.
If this problem is too difficult you can also assume that profit from all objects is the same ,i.e., one. (I added this constraint because I came across a problem somewhere and that perfectly fit into this type of problem where profit from all objects was same. That's how i started wondering about this topic).
If you have multiple sacks say n you will need that many states.lets consider you have n sacks then your dp will look like: dp[index][cap1][cap2]..[capn]=max( dp[index-1][cap1]...[capn], dp[index-1][cap1-wt[i]] + profit[i], dp[index-1][cap1]..[capn-wt[i]] + profit[i] );
I dont know how to simplify this furthur
You can do something like this CSES problem and solve in O(n * 2^n), the idea is to use DP to go through all permutations in less than n!. You can also do n * w^(sacks) by just adding more dimensions