# Tag Info

## Hot answers tagged knapsack-problems

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

• 81.9k
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.5k
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.5k

### 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,479
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.5k

### 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,187
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
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,677
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 ...
• 4,322

### 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 ...
• 72.6k
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,561

### 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,521
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.4k

### 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,658
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 ...

### 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.
• 278k

### 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 ...
• 30.5k

### 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
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, ...
• 161k
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
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.6k
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 ...
• 161k
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 ...