0
$\begingroup$

Just to be clear:

I have a set of items of lengths $x_{i}$

I want to choose a set of these items such that I maximize their sum, but ensure that their sum is less than some quantity S.

$$ max\sum_{i=0}^{N}c_{i}x_{i} < S $$

I'm looking for an algorithm to get a solution. So far, I've come up with a basic greedy algorithm (continually add the largest element that fits), and combinatoric, brute force method. I figure the first one is too inaccurate and the latter is incalculably slow ($i <10$, but $c_{i} > 50$ on average in my case).

Online, I've found Ingargiola and Korsh's algorithm (1977), and that's about all. I'd like to know if there's other algorithms out there, what their respective time complexities and accuracy are (if possible) and where I can learn more about them.

Note: I'm a university student so I have access to most online journals.

Thanks

$\endgroup$
  • $\begingroup$ Your greedy algorithm is not in fact an algorithm for this problem, for it does not produce a solution ("maximize their sum"). Because of this, I'm not quite certain what you're looking for. Would a 2-approximation that runs in, say, quadratic time be of interest? Note that if you constrain the $c_i$ to each be $0$ or $1$, a solution to this problem (if you change inequality to equality) also gives a solution to the subset-sum problem. That suggests that it's fundamentally hard. $\endgroup$ – John Hughes Jun 22 '17 at 18:07
1
$\begingroup$

This Knapsack question is NP-hard, meaning that there does not exist a polynomial-time algorithm that produces the optimal solution on worst-case inputs, unless $P=NP$.

However, the problems admits a polynomial-time approximation scheme (PTAS), meaning that for any $\varepsilon>0$, there exists an algorithm that runs in time $poly(n)\cdot f(\varepsilon)$, with $f(\cdot)$ being possibly an exponential function depending only on $\varepsilon$, such that the resulting solution is within $\varepsilon$ of the actual optimal solution.

For practical consideration, a discretization method can be used to transform each $x_i$ to integers, and to apply dynamic programming on the discretized data. This algorithm runs in linear time of $n$, but its running time depends inverse polynomially ($1/\varepsilon$) on the discretization error.

You may also wish to consult the wikipedia page on the Knapsack question for more details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.