1
$\begingroup$

I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal.

More formal definition of the problem from a Wikipedia article on KPs:

If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:

maximize $\sum_{j=0}^n x_j$

subject to $\sum_{j=0}^n w_jx_j \leq W$,

$x_j \in \{0, 1\}, \forall_j \in \{1, ..., n\}$

I skimmed through Knapsack Problems book (Kellerer et al', 2004) that is referenced by that Wikipedia article but couldn't find that particular problem.

I also saw some posts about this exact problem with no good answers:

The answer to the first post mentions Capital Budgeting problem, but the provided link doesn't discuss the case where all profits (values) are equal, which I believe can be better optimized due to its special case.

The answer to the second post mentions a naive solution in which a greedy algorithm picks minimum weight items at each step until no more items fit in the knapsack. This requires knowing the order of items by weight, which results in $O(n\log{n})$ solution.

Is there an algorithm with a better upper bound (e.g. linear time)?

$\endgroup$
  • $\begingroup$ Define a tie breaking procedure for weights that consistently breaks ties between equal weighted items (e.g. which is described first in the input). Pick a random element k, see if the sum of weights of all elements no heavier than k than is less than W. If so, keep all those elements and recurse on the subproblem of elements heavier than k, with W decreased appropriately. Else, discard the larger elements and recurse with the same W. Each round is linear in instance size, but each round is smaller than the previous by a const. factor in expectation so the total running time is expected linear $\endgroup$ – Yonatan N Oct 28 '18 at 0:48
  • $\begingroup$ @YonatanN Thanks! This is great; you could've posted this as a proper answer :) $\endgroup$ – user95635 Oct 28 '18 at 3:18
0
$\begingroup$

Comment $\rightarrow$ answer.

Without loss of generality, we assume that all weights are strictly positive (otherwise, we can take all non-positively-weighted items ahead of time and change $W$ as appropriate).

From here, one can use an approach reminiscent of Randomized Quick-Select to solve this in expected linear time. First, define a tie breaking procedure for weights that consistently breaks ties between equal weighted items. For example, one can use the ordering of items as given in the input.

Now repeat the following procedure. Pick a random element $k$ and check if the sum of weights of all elements no heavier than $k$ (using the above tie-breaking rules) is less than $W$. If so, the optimal solution must contain all such elements, so put them all aside and recurse on the subproblem of elements heavier than k, with $W$ decreased appropriately. Otherwise, the optimal solution must be a strict subset of these elements, so discard all larger elements and recurse with the same $W$ you started with. The base case of the recursion is one where you return the empty set when $W$ is less than the cost of the cheapest item (or if no items remain).

Each round takes time linear in the input size for that round, but it takes a constant number of rounds (in expectation) to reduce the size of the instance by a constant factor, so the total running time intuitively should be expected linear. Indeed, the usual analysis of Randomized Quickselect works identically here, too, proving the result.

Here's a non-tail-recursive implementation in Python.

def uniformKnapsack(items, W):
    import random

    def subProcedure(remaining, new_W):
        # base case
        if remaining == [] or min(i[0] for i in remaining) > new_W:
            return []

        # sample random item
        random_item = random.choice(remaining)

        # split input into larger and smaller subsets based on the item
        smaller = [i for i in remaining if i < random_item]
        not_smaller = [i for i in remaining if random_item <= i]

        # compute the total cost of all smaller items
        smaller_cost = sum(i[0] for i in smaller)

        if smaller_cost <= new_W:
            # include all smaller elements and recurse on the rest with a smaller W
            return smaller + subProcedure(not_smaller, new_W - smaller_cost)
        else:
            # recurse on the smaller subset with the same W
            return subProcedure(smaller, new_W)

    # convert a list of items (a, b, c) to  a list of the form ((a, 0), (b, 1), (c, 2)) for
    # consistent tie breaking in comparison operations
    augmented_items = [(j, i) for (i, j) in enumerate(items)]

    # compute the solution over the augmented items
    solution = subProcedure(augmented_items, W)

    # return the un-augmented items from the solution
    return [i[0] for i in solution]
$\endgroup$
  • $\begingroup$ I meant that your comment was sufficient for me as an answer; you could have just pasted it as-is here :) Anyway, thanks for elaborating. I hope this will be helpful to others. I wrote a similar algorithm, but instead of selecting random k, I select median k using median of medians (in linear time). This way guaranteed worst-case performance is linear using Master Theorem. With random k you can argue that worst-case performance is quadratic if you get very unlucky and select the most extreme k every time (basically, the same argument as to why worst-case of Quicksort is quadratic). $\endgroup$ – user95635 Nov 3 '18 at 12:04
0
$\begingroup$

Sorting the weights takes O (n ln n), but you don't need to sort them completely.

We start with the quicksort algorithm. If necessary, modify the partitioning algorithm so that portioning always separates an array into a "smaller" portion and a "larger" portion, that is all elements are exactly in one of these portion.

If the smaller elements all fit, then we put them into the knapsack without sorting them, then we handle the larger elements recursively. If the smaller elements don't all fit, then we can completely ignore the larger elements, and partition the smaller ones again.

$\endgroup$
  • $\begingroup$ Same idea as Yonatan's answer. Thanks :) $\endgroup$ – user95635 Nov 3 '18 at 12:07

Your Answer

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