Re: Subset sum problem

"John P. Green" <xyzzy35@xxxxxxxxxxx> writes:

> I have a variation of the subset sum problem I want to solve:
>
> Given a finite set W of real numbers, of cardinality n,
> real number s, and integer k <= n, find a subset of W
> of cardinality k whose sum is as close as possible to s.
>
> This problem is I'm sure NP-complete,

Indeed, as a solution to this problem will also give a solution to the
subset sum problem.

> I'd like to know what approximation algorithms are available.

If you have a subset sum approximation, you can use this to
approximate your problem:

1) Convert the reals to integers (possibly scaling them to get more
digits of precision).

2) Find approximative subset sum.

You can increase the scaling to increase precision.

Torben

.

Relevant Pages

  • Re: [QUIZ] Splitting the Loot (#65)
    ... However, if we consider the Subset Sum problem: given a set of integers and an integer k, find a subset whose sum is k? ... We can apply a subset sum algorithm to find the possible subset that sums to the fair share for the first "pirate", and then work in the same way on the remaining elements for the other pirates. ... If the subset sum algorithm finds the treasures for the first pirate it is impossible to divide the remaining treasures among the remaining two pirates even though ...
    (comp.lang.ruby)
  • Re: Summing numbers from a list to a goal
    ... Look up the Subset Sum problem (similar to ... Knapsack). ... The Wikipedia site has good and easy to understand info. ...
    (comp.programming)