CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Junior Member
Join Date
Apr 2012
Posts
1

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

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.

2. Elite Member
Join Date
May 2009
Posts
2,413

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

Originally Posted by klocuch12
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?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•