16
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 ...
- 13.2k
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 ...
- 38.6k
6
votes
Find max total revenue in a directed graph
Your problem can be solved by reducing it to a min-cost max-flow problem where a unit of flow represents one unit of commodity. A negative cost represents a profit.
Create a directed graph containing $...
- 28.2k
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,807
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 ...
- 984
4
votes
Accepted
01 Knapsack with selection of items with minimum total weight
Sure. It's easy to take any algorithm to solve the ordinary knapsack problem, and apply it to your problem. In the ordinary knapsack problem, we specify an upper bound on the weight. Once we find ...
D.W.♦
- 156k
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 $...
- 81.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 ...
- 28.2k
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,459
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$ (...
- 28.2k
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 ...
- 5,793
3
votes
Accepted
Contained optimal combination of inputs
It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar ...
- 4,222
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,657
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,501
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 ...
- 72k
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 ...
- 81.4k
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 ...
- 356
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.♦
- 156k
3
votes
Multiple Knapsack using Dynamic Programming
When all values are 1 and all capacities the same, this is the bin-packing problem, which is Strongly NP-Complete. Therefore, a sensible DP solution is probably not possible unless P=NP.
For very ...
- 2,469
3
votes
Accepted
SAT to knapsack vs. ETH
Knapsack does not have any known quasipolynomial time algorithm (one which runs in
$n^{poly(\log n)}$ time, with $n$ being the inputs length).
What it does have is a pseudo-polynomial time algorithm, ...
- 13.3k
3
votes
Fantasy premier league dream team algorithm?
You can formulate an integer program for this problem. For each player $i$ let $a_i$ be the number of points the player scored, $p_i$ is his price. Moreover, let $G, B, M, F$ be the set of goal ...
- 1,583
3
votes
Accepted
DP recurrence relations: Coin change vs Knapsack
The knapsack problem only allows you to add each item once. Subtracting from $k$ is, in a sense, iterating through the items and resolving a different one each recursion.
Put another way, if you ...
- 318
3
votes
Non-existence of approximation algorithm for the knapsack problem
Given an instance of knapsack, multiply all values by $k+1$. Any solution satisfyign $OPT(I) - P_A(I) \leq k$ is in fact optimal, so you could use such an algorithm to solve knapsack.
- 275k
3
votes
Accepted
Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed
This problem is NP-hard by a reduction from partition.
Let $X = \{x_1, \dots, x_n\}$, be an instance of partition and let $2M = \sum_{x \in X} x$ (assume that $M$ is an integer as otherwise the ...
- 28.2k
3
votes
Knapsack with a fixed number of weights
In your case that the sizes are only 1, 2 or 4, the answer is quite easy:
If the knapsack has an odd size, then you pick the most valuable item of size 1 and add it to the last slot.
If the ...
- 28.3k
3
votes
0-1 knapsack problem with minimum and maximum weight capacity
We can change the definition of the traditional Knapsack to "the maximum value we can get from the first n items using exactly W ...
- 53
3
votes
Accepted
Detecting conservation, loss, or gain in a crafting game with items and recipes
This should be solvable with linear programming.
Background and setup
Let the state vector be a vector of the count of number of each item you have. If the possible items are milk, wheat, sugar, ...
D.W.♦
- 156k
3
votes
Accepted
Distribution of resources from providers to maximum number of receivers
This problem is a case of maximum flow problem.
Suppose we are given internet providers $p_1, p_2, \cdots, p_m$ and residents $r_1, r_2, \cdots, r_n$. Consider a flow network specified as the ...
- 38.6k
Only top scored, non community-wiki answers of a minimum length are eligible