-1

I am trying to write a c# program that does following:

  1. Takes two parameters: a list of objects and a number
  2. Iterates through the list and find the first set of objects that equals to the number.
  3. Stop iteration if a set is found and the return the set.

So, I have a list of user defined object, say Person as an example. Say, Person object has two fields, Name and age. For example, 

MyList
-   Person1: John, 10
-   Person2: Mary, 25
-   Person3: Mike, 35
-   Person4: Ann, 20
-   Person5: Joe, 5

I want to find a set from the list that equals to the number that I am passing in. If I am passing in above list and 50, I want to return Person2, Person4, Person5 as a list.

EkoostikMartin
  • 6,831
  • 2
  • 33
  • 62
Tony
  • 3,319
  • 12
  • 56
  • 71
  • 1
    This sounds like a homework question. – Dustin Kingen Aug 07 '13 at 13:22
  • 5
    You say you are "trying to write", so show us what you have tried, and what doesn't work. – EkoostikMartin Aug 07 '13 at 13:23
  • 3
    @Romoku: Which in itself is not a problem. The problem here is that the OP didn't try anything himself or at least he doesn't show us what he tried and what the problems with this were. – Daniel Hilgarth Aug 07 '13 at 13:23
  • 1
    The keyword to search here is "0/1 knapsack problem". – Sergey Kalinichenko Aug 07 '13 at 13:23
  • Why wouldn't you want to return Person1, 3 and 5? 10 + 35 + 5 is also 50. – Daniel Hilgarth Aug 07 '13 at 13:24
  • 2
    This us [Subset Sum Problem](http://en.wikipedia.org/wiki/Subset_sum_problem). It is NP-Complete and can be solved using brute force on `O(2^n)` or using DP on `O(W*n)`, where `n` is the number of elements in the input set, and `W` is the input number. – amit Aug 07 '13 at 13:25
  • Sorry everyone that I wasnt clear. I was just thinking it and wasnt clear how I could achieve this. I will look at both knapsack and subset sum. – Tony Aug 07 '13 at 13:34

1 Answers1

0

This is subset sum problem.

Unfortunately, it is NP-Complete, so there is no known polynomial solution for it.

However, it does have a pseudo-polynomial solution, using Dyanamic Programming, that is using the next recursive function:

f(i,0) = true
f(0,k) = false (k != 0)
f(i,k) = f(i-1,k) or f(i-1,k-weight[i])

Running with f(n,W) yields true if such solution exists, and false otherwise.

The dynamic programming solution fills up a table, after the table is full, you need to "retrace" your steps from table[n][W] back in order to find which items should be included in the set.
More information on getting the actual elements from the table can be found in this thread

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333