Questions tagged [knapsack-problems]

A problem in combinatorial optimization. Given a set of items with both weight and value, determine the number of each item to include in a collection so that the total weight is at most a given limit and the value of the collection is maximized.

Filter by
Sorted by
Tagged with
11
votes
2answers
24k views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
11
votes
1answer
14k views

Variant of the knapsack problem

How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $...
5
votes
0answers
608 views

2 Dimensional Subset Sum: looking for information

I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
4
votes
1answer
2k views

The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? ...
8
votes
1answer
6k views

Balanced Weight Distribution in Bins/Buckets

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which is ...
7
votes
1answer
1k views

Knapsack with same value

I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight ...
4
votes
4answers
3k views

Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

On the wikipedia page for the knapsack problem it says that the runtime is $\mathcal{O} (nW)$ and goes on to say that this doesn't violate its classification as NP because the input size is related to ...
3
votes
1answer
4k views

Dynamic Programming Solution to 0,1 KnapSack Problem

I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course ...
3
votes
0answers
972 views

Finding the n-best items in a 0/1 Knapsack

I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: ...
1
vote
1answer
147 views

What makes an MILP problem solvable?

Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
1
vote
1answer
2k views

Use dynamic programming to find a subset of numbers whose sum is closest to given number M

Given a set $A$ of $n$ positive integers $a_1, a_2,\ldots, a_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying ...
0
votes
1answer
405 views

Psedu-polynomial Time : Conflict with the definition of input size

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
9
votes
1answer
428 views

What algorithms exist for solving natural number linear systems?

I'm looking at the following problem: Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number ...
4
votes
2answers
832 views

What's the big deal with the knapsack problem?

In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic ...
2
votes
1answer
547 views

A special case for the subset sum problem

If we wanted to see if any disjointed subset of a set $X = [w_1, ..., w_n]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution ...
2
votes
2answers
151 views

Distribution Optimization Algorithm

I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem). Problem Imagine StackOverflow started offering a subscription where ...
1
vote
1answer
91 views

Getting output of dynamic programming, (contiguous sub array, box stacking)

I am attempting to output the largest stack of boxes given an input of a set of boxes. Currently I have an array called maxWeight that has the values of the boxes sorted from largest to smallest, this ...
1
vote
2answers
1k views

What's the time complexity bound for the Knapsack with real weights?

Let's start with the formalism: Let $W$ be the total weight of our bag, $1,...,n$ be our elements, $w_1,...,w_n$ their corresponding weights, and $v_1,...,v_n$ their corresponding values. As is ...
1
vote
0answers
357 views

Reducing a problem with two knapsack that needs equal number of items from Knapsack?

I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness. The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from ...
0
votes
1answer
670 views

A special case for the subset sum problem: selecting from powers of two

Given a multiset $X=\{x_1,\dots,x_n\}$ where every element $w_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$. (This question is ...
0
votes
0answers
71 views

Get the maximum sum of n items below a threshold

Consider a modified Knapsack Problem where: The number of items to be included is fixed. The value of each item is equal to its weight. Therefore, given a set of numbers, a threshold and the number ...
0
votes
1answer
285 views

Knapsack variant

In my line of work, I have encountered the following variant of discrete knapsack and I was wondering if it has already been studied. E.g. We are given a set of 3 items (A,B,C). The goal is to ...