2 Replies - 1019 Views - Last Post: 11 September 2009 - 09:56 AM

#1 Some1Wow   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 11-September 09

Need Algorithim name for a problem

Posted 11 September 2009 - 12:58 AM

Hello everyone

I did not take an algorithims course so I need your help

Is there an algorithim to solve this problem? .

if I have a set of items and each item has a subset of items with a value.
I want to find the best solution , have an item from each subset where the sum of the items <= a given number

Example:
I have 3 items:
item1 has > p 1 : value =3
p 2 : value = 4

item2 has > p1:value = 5
p2 : value =4

item3 has > p1:value = 3
p2 : value =6

and I have a given number 12
Best Solution : item1 : p2 - item 2 : p1 -item3: p1
Sum=12 <=12

I want an algorithim name that solves this problem similar to Knapsack - Sum of subset .....etc
or any algorithim that helps me solve this solution

I just need the name of algorithim not the code!


Thanks

This post has been edited by Some1Wow: 11 September 2009 - 01:04 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Need Algorithim name for a problem

#2 Kanvus   User is offline

  • D.I.C Regular
  • member icon

Reputation: 42
  • View blog
  • Posts: 452
  • Joined: 19-February 09

Re: Need Algorithim name for a problem

Posted 11 September 2009 - 09:23 AM

the way you're explaining it is hard to visualize
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Neumann*


Reputation:

Re: Need Algorithim name for a problem

Posted 11 September 2009 - 09:56 AM

Not every algorithm has a name. You are asking for something that may not exist.

This does seem to be very similar to the Knapsack problem, except that you can only take a single element from each subset, at most. If I were you, I would check out the algorithm for the Knapsack problem to see if I can tweak it to work with your case. A simple brute-force can also solve this.

This post has been edited by Neumann: 11 September 2009 - 09:57 AM

Was This Post Helpful? 0

Page 1 of 1