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
25k 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
15k 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
615 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? ...
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 ...
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
0answers
986 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
148 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
432 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
431 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
858 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
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 ...
2
votes
1answer
552 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 ...
1
vote
1answer
92 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
0answers
372 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 ...
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 ...
0
votes
1answer
289 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 ...
0
votes
1answer
685 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 ...