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 ...
user avatar
9 votes
Accepted

What algorithms exist for solving natural number linear systems?

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = ...
user avatar
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)$ ...
user avatar
  • 1,602
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 34.1k
6 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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 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 \...
user avatar
5 votes

Find non-overlapping scheduled jobs with maximum cost

One could implement this in O(nlogn) Steps: Sort the intervals based on end time define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. ...
user avatar
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 \{...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 70.9k
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 ...
user avatar
  • 1,914
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 $...
user avatar
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 ...
user avatar
  • 23.4k
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 (...
user avatar
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$ (...
user avatar
  • 23.4k
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 ...
user avatar
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 ...
user avatar
  • 141k
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; \...
user avatar
  • 70.9k
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 ...
user avatar
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 ...
user avatar
  • 22.1k
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 ...
user avatar
  • 217
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 70.9k

Only top scored, non community-wiki answers of a minimum length are eligible