# Tag Info

## Hot answers tagged knapsack-problems

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 ...
• 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

• 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 ...
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

• 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