Skip to main content
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 ...
Dylan Black's 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 ...
John L.'s user avatar
  • 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 $...
Steven's user avatar
  • 29.5k
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 ...
David Eisenstat's user avatar
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 ...
Mathieu Mari's user avatar
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.'s user avatar
  • 161k
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 $...
David Richerby's user avatar
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 ...
Steven's user avatar
  • 29.5k
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 ...
Steven's user avatar
  • 29.5k
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 (...
j_random_hacker's 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$ (...
Steven's user avatar
  • 29.5k
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 ...
Inuyasha Yagami's user avatar
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 ...
quicksort's user avatar
  • 4,272
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 ...
Karolis JuodelÄ—'s user avatar
3 votes
Accepted

Proof of 0/1 knapsack optimal substructure

Suppose that some $S'\subseteq E-\{x\}$ is a better admissible solution than $S-\{x\}$. Then $S'\not= S$, the value is more, $v(S') > v(S-\{x\})$, and $x\not \in S'$, and $w(S')\leq W-w(x)$, as you ...
Lieuwe Vinkhuijzen's 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 ...
Raphael's user avatar
  • 72.6k
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. ...
hengxin's user avatar
  • 9,561
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 ...
Albert Hendriks's user avatar
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, ...
Ariel's user avatar
  • 13.4k
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 ...
ttnick's user avatar
  • 1,658
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 ...
ConcernedCitizen's user avatar
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.
Yuval Filmus's user avatar
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 ...
gnasher729's user avatar
  • 30.5k
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 ...
aghx99's user avatar
  • 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.'s user avatar
  • 161k
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 ...
John L.'s user avatar
  • 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 ...
Juho's user avatar
  • 22.6k
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.'s user avatar
  • 161k
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 ...
Bernardo Subercaseaux's user avatar

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