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 ...
- 39.1k
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 $...
- 29.6k
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
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
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.♦
- 166k
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 $...
- 82.2k
4
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 ...
- 29.6k
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 ...
- 29.6k
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,509
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$ (...
- 29.6k
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 ...
- 6,267
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,511
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.6k
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,272
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,641
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,687
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,866
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.
- 279k
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 ...
- 31.6k
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.♦
- 166k
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 ...
- 39.1k
3
votes
Accepted
FPT algorithm for Knapsack
The reference you should have found is [1], where the authors consider several parameters and also higher dimensional knapsack problems (see e.g., Table 1 for a list of running times for different ...
- 22.8k
3
votes
Accepted
Random splitting with fixed size range
The number of solution sets of size $k$ is either uncountably infinite (and in particular has the same cardinality as $\mathbb{R}^{k-1}$), 1, or 0.
So, the following algorithm works:
If there is any ...
D.W.♦
- 166k
3
votes
Accepted
knapsack with graph connectivity constraints
There shouldn't be a pseudopolynomial-time algorithm; the problem is NP-hard even if all values are given in unary. We can reduce from the $\textsf{Connected Vertex Cover}$ problem in which we need to ...
- 1,281
3
votes
Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval
You're right. It is a sort of 0-1 knapsack problem. It is NP-complete in general. So you will need to settle for approximate solutions or heuristics or algorithms that only work for short strings ...
D.W.♦
- 166k
2
votes
Accepted
A special case for the subset sum problem: selecting from powers of two
First, look at the bits that are set in $M$ and write it as $M = m_1+m_2+\dots$ where each $m_i$ is a power of two and such that $m_1$ is the smallest power of two, and so on.
If the numbers $x_i \in ...
- 135
Only top scored, non community-wiki answers of a minimum length are eligible