15
votes
Accepted
Why is the dynamic programming algorithm of the knapsack problem not polynomial?
When we say polynomial or exponential, we mean polynomial or exponential in some variable.
$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a ...
8
votes
Accepted
Dynamic Programming Solution to 0,1 KnapSack Problem
The key to understanding a dynamic programing problem is understanding the recursive definition and this can be daunting. For this problem we start with n objects labeled 1 to n.
We define $O(K,W)$ ...
- 1,602
7
votes
Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?
Polynomial time means that the running time is bounded by a polynomial in the length of the input. The running time here is bounded by $nW$. $n$, the number of items, is surely less than the ...
- 80.4k
7
votes
Knapsack Greedy Approximation: Worst Case
The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been ...
- 270k
7
votes
Accepted
Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?
There is no guarantee that the packing algorithm you suggested will lead to an optimal packing. Say you have two knapsacks of capacity 5, and objects of size 1, 2, 3 and 4. An optimal packing would be ...
- 156
7
votes
Accepted
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
You are on the right track.
It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding ...
- 34.9k
6
votes
Accepted
The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?
$n$ is not part of the input, $n$ denotes the number of objects in the input.
The input consists of the capacity of the knapsack, a list of objects, each with a value and weight. If there are $n$ ...
5
votes
Accepted
Find 8 numbers whose sum is closest to a defined value
Dynamic programming
One approach is to use dynamic programming. If you have $n$ numbers ($n$ rows in the file), and each number is in the range $1..m$, then the obvious dynamic programming algorithm ...
D.W.♦
- 143k
5
votes
Accepted
Subset sum algorithm in O(n³ log n)?
This is a common misconception many have. Subset sum, among others, is NP-complete only if the input is encoded in binary (or ternary etc). In unary encoding it's polynomial-time solvable by a simple ...
- 1,841
5
votes
Accepted
Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?
The input to 0/1 knapsack is a list of $n$ items each with a weight $w_i$ and value $v_i$ with knapsack size $W$ and maximum value $V$. Thus the input list has size $O(n (\log W + \log V))$.
So $n \...
- 17.3k
5
votes
Accepted
Minimize a sum with a weight constraint
The problem you have given is similar to KNAPSACK as Yuval Filmus mentioned.
KNAPSACK problem is defined as:
maximize $\sum_{i=1}^n v_i x_i$
subject to $\sum_{i=1}^n w_i x_i \leq W$ and $x_i \in \{...
- 4,747
5
votes
Accepted
Smallest cost in weighted directed graph with combinations
You can formulate problems like this as an integer program and apply off-the-shelf tools to find (near) optimal solutions.
The example is rendered something like this (the exact syntax depends on the ...
- 974
4
votes
What's the big deal with the knapsack problem?
I think mainly the techniques that are covered in that section (dynamic programming and greedy algorithms) are very important.
There are several other properties. First of all, integral knapsack ...
- 1,914
4
votes
Brute force method to solve the 0-1 knapsack problem
You can't. Landau notation does not hold enough information.
You don't know the constant factor(s).
With only $O$, you don't have a lower bound.
It's only a worst-case bound; different runs with the ...
- 71.1k
4
votes
Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution
As you're aware, "polynomial time" means that there is a polynomial $p$ such that the running time on input $X$ is at most $p(|X|)$.
An input to the knapsack problem consists of a list of $...
- 80.4k
4
votes
Accepted
Knapsack Problem with exact required item number constraint
You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be ...
- 23.9k
4
votes
Detecting conservation, loss, or gain in a crafting game with items and recipes
Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (...
- 5,164
4
votes
Accepted
Dynamic Programming - Thief Variation Probem
For $i=1,\dots,N$, and $r \in \{S,R,B\}$
define $OPT[i,r]$ as
the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints:
If $x=S$ (...
- 23.9k
4
votes
0/1 knapsack problem: Greedy Algorithm Counterexample
Consider this counterexample. Suppose the knapsack has a capacity 4. And suppose there are three items:
Item A with weight 3 and value 5
Item B with weight 2 and value 3
Item C with weight 2 and ...
- 3,976
3
votes
Why is the dynamic programming algorithm of the knapsack problem not polynomial?
I have read that one needs $\lg W$ to represent $W$ so it is exponential-time. But, I don't understand, also one needs $\lg n$ to represent $n$, no?
This is a great question. You need to look at ...
- 80.4k
3
votes
Accepted
Optimizing NFL draft picks
Yes, this can be solved using a dynamic programming algorithm very similar to the standard dynamic programming algorithm for the knapsack problem.
Basically, order the positions from 1 to 9. You're ...
D.W.♦
- 143k
3
votes
Accepted
Brute force method to solve the 0-1 knapsack problem
As O(2^n) says adding one item will double computation time, giving the fact that one day equals 2^16 seconds, you more or less answered the question yourself.
A method solving a problem with 20 ...
- 217
3
votes
How to make the standard DP algorithm for 0/1 Knapsack make larger steps?
Your assumption is wrong; the dynamic programming algorithm does not do that. It computes $m(n,W)$ according to the recurrence
$\qquad\displaystyle
m(i,w) = \begin{cases}
0, &i=0 \lor w=0; \...
- 71.1k
3
votes
Accepted
What makes an MILP problem solvable?
You may be interested in reading about total unimodularity. An ILP is solvable in polynomial time if the associated matrix is totally unimodular (sufficient but not necessary condition). This explains ...
3
votes
Accepted
Output of well-known algorithms for the Subset sum problem
The question "is there a subset that sums up to $t$?" has a YES/NO answer. In general, we shouldn't expect an algorithm to do more than it is asked to, so to speak. However, it is rather common that ...
- 22.1k
3
votes
Subset sum problem with many divisibility conditions
This problem can be solved in polynomial time using linear programming, and this is actually true for any partial order $(S,\le)$. By the way, we can prove by induction that for any finite partial ...
- 366
3
votes
Why is OPT at least the most valuable item for FPTAS Knapsack?
It is common to assume without loss of generality that the maximum item weight is at most as large as the knapsack capacity. That is okay (in the context of complexity theory) because filtering out ...
- 71.1k
3
votes
Accepted
Two recurrences for the change-making problem with repetition
First, the number of subproblems and dependencies among these subproblems for the first recurrence are $v$ and $nv$ respectively, while they are $nv$ and $2nv$ respectively for the second one.
...
- 9,219
3
votes
Accepted
A special case for the subset sum problem
Obviously, even numbers cannot add up to an odd $M$. Other than that, we could just set $v_i = w_i /2$ and $N = M/2$. Then finding a subset of $w_1, \dots w_n$ which adds up to $M$ would be the same ...
- 3,577
Only top scored, non community-wiki answers of a minimum length are eligible