Bounded knapsack problem DP solution in O(W) space?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

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

  1. #1
    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. #2
    Join Date
    May 2009
    Posts
    2,413

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

    Quote Originally Posted by klocuch12 View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center