2 Replies - 960 Views - Last Post: 16 March 2016 - 07:51 AM

#1 Hitnrun   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 15-March 16

Knapsack Variation

Posted 15 March 2016 - 05:56 PM

To start sorry for my bad english.
I have in hands what I think is a variation of the knapsack problem:
It's given the number "max" of hours to maximize and the values of that for example
1 1 3 machine 1 works 1 hour and the value is 3 (so I need to maximize the value)
1 2 5
2 2 1
2 1 2

So if I want to maximize that for w=3 I use knapsack and so on. But there is a catch I can't pass in the same machine 2 times (and using the knapsack 1/0 I can pass in the same machine multiple times.
I just wanted to anyone show me the way (theoretically) how to solve this problem.
I organized my data (yeah the data comes not organized - I organized by ID number) but from there I just can't move on

Is This A Good Question/Topic? 0
  • +

Replies To: Knapsack Variation

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7915
  • View blog
  • Posts: 26,425
  • Joined: 05-May 12

Re: Knapsack Variation

Posted 15 March 2016 - 08:14 PM

I think you misunderstood the 0-1 knapsack problem (or maybe I am because of lack of sleep). But as I understand things, with the 0-1 knapsack problem, you can only pick an item once or not at all. You can't have multiple copies of that item.

Anyway, moving this to Computer Science since there is nothing C specific here and all you are looking for ar ways to attack the problem -- not code.
Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12800
  • View blog
  • Posts: 45,992
  • Joined: 27-December 08

Re: Knapsack Variation

Posted 16 March 2016 - 07:51 AM

Skydiver is correct. The 0-1 Knapsack variant permits at most one instance of each item to be used.

As for solutions, have you done any research yourself? There are many algorithms that are easy to find, including those on the Wikipedia Page.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1