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.2k
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.8k
5
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,297
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
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.6k
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.8k
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.8k
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$ (as ...
- 29.8k
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 ...
- 2,033
3
votes
What are some concrete (near-)"worst-case" examples of subset-sum?
It's not clear how to formally define worst-case (or near-worst-case) instances, but here is something you could try.
The idea is to combine the following two tidbits:
We know some hard instances for ...
- 281k
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
0/1 Knapsack problem with real-valued weights
Sort the items by density such that $p_1/w_1\geq p_2/w_2\geq\cdots\geq p_n/w_n$ for profits $p$ and weights $w$. Let $W(k)=\sum_{1\leq i\leq k} w_i$ be the total weight of the first $k$ items in this ...
- 620
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.
- 281k
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 ...
- 32.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.♦
- 169k
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.2k
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 ...
- 23k
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.♦
- 169k
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,605
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.♦
- 169k
3
votes
Knapsack with both upper and lower capacity
According to Computers and Intractability by Garey and Johnson I assume that both values and costs are positive.
Apart from trivially unsolvable case of $L > \sum_{i = 1}^n c_i$, depending on a gap ...
- 1,108
2
votes
Multiple Constraint Knapsack Problem Dynamic Programming
Yes. More precisely, for any fixed number of constraints (for example, weight and volume) the problem has a pseudo-polynomial time algorithm based on dynamic programming.
The idea in your comment (...
- 3,479
2
votes
Multi- Knapsack problem variation
The simplest approach is to formulate this as an instance of integer lienar programming. You have zero-or-one variables $x_{i,j}$, where $x_{i,j}=1$ means that item $i$ is placed into knapsack $j$. ...
D.W.♦
- 169k
2
votes
Is a Knapsack Problem with only Color Constraints NP-Complete?
So, items have only 2 parameters:
Color. I assume that each item has one color ("one of C colors"). If not, this problem is probably $\mathsf{NP}$-hard.
Price.
Now we need to pack a knapsack to ...
- 2,131
2
votes
Accepted
Knapsack problem question
First row indicates the optimal knapsack for each weight using only that item. Then each subproblem in that row asks what is the maximal value one can reach with using only first item and maximum ...
- 421
2
votes
Accepted
Psedu-polynomial Time : Conflict with the definition of input size
First, the size of the input is the number of bits required to represent the input. When talking about complexity, we often assume that our input is represented as some bit-string.
For the knapsack ...
- 8,462
2
votes
How to solve this very complicated assignment problem
I don't see a way to solve this using standard algorithms for the assignment problem.
If you want an exact solution (i.e., the optimal solution), I would recommend integer linear programming (ILP). ...
D.W.♦
- 169k
Only top scored, non community-wiki answers of a minimum length are eligible