Bounded knapsack problem DP solution in O(W) space?

[klocuch12]

Hello,

I am currently working at the system which is meant to do some sort of optimization - what kind of is not particularily important. What is important is that I am essentially solving a knapsack problem of discrete kind. There are well known solutions to this problem, but due to strict memory constraints (there are 8000 registers available altogether, whereas there can be up to 6000 capacity units to distribute) most of these go out of the window. One acceptable solution is DP (dynamic programming) one.

The issue is, that knapsack problem in that case is bounded (limited amount of items of each kind of can appear in a solution), whereas DP solution doesn't seem to discriminate, how many items of specific kind are contained within an optimal subset. Is there any workaround? I have figured out, that first kind of item can be "artificially" limited (basically, you make a for loop just for the first kind, so if you have, say, 2 items with weight 300, and capacity is 1000, you can fill everything above 2*300 = 600 with just that value. So tab[900] would not be 3*300 = 900, but 2*300). The problem? Of course, you only can handle one constraint like that. Are there modifications of DP algorithm, which:

1)Handle all constraints like that (or just more than one, as there will be max 6 kinds of items)?

2) Still work within O(W) space (remember - registers are limited)?

Thank you in advance for help.

[nuzzle]

The issue is, that knapsack problem in that case is bounded

Well, the bounded knapsack problem is a standard problem in its own right. Have you searched for a DP solution? Or some other solution strategy for that matter?