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
Knapsack Variation
Page 1 of 12 Replies - 960 Views - Last Post: 16 March 2016 - 07:51 AM
Replies To: Knapsack Variation
#2
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.
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.
#3
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.
As for solutions, have you done any research yourself? There are many algorithms that are easy to find, including those on the Wikipedia Page.
Page 1 of 1

New Topic/Question
Reply


MultiQuote





|