# Tagged Questions

A problem in combinatorial optimization. Given a set of items with both weight and value, determine the number of each item to include in a collection so that the total weight is at most a given limit and the value of the collection is maximized.

39 views

### can we solve dynamic knapsack problem using Memoization approach?

As we know Dynamic programming has two techniques. Bottom up dynamic programming approach. Top down memoization approach Normally dynamic knapsack problem is solved using Bottom up dynamic ...
58 views

### Running time of naive recursive implementation of unbounded knapsack problem

How does one go about analyzing the running time of a naive recursive solution to the unbounded knapsack problem? Lots of sources say the naive implementation is "exponential" without giving more ...
32 views

### Knapsack: there is a polynomial solution in bit terms?

I'm reading about Knapsack problem. The approaches to solve that I found: Branch and bound Brute force Dynamic programming Memory functions Greedy All solutions have exponential time in terms of ...
44 views

### Two recurrences for the change-making problem with repetition

The change-making problem with unbounded repetition is: Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$; and an amount $v$. Output: Can the given $v$ amount of money be ...
47 views

### 0/1 Knapsack problem with overlapping items

Here's a doozy: Given a knapsack with a capacity W, and n overlapping items (definition of overlapping to follow), which items should we take to maximize the value of the knapsack? In this problem, ...
38 views

65 views

### What type of knapsack problem is this?

I need to choose the highest value combination of items given a specific set of constraints. These constraints are: Exactly 6 items from group A and 2 items from group B must be selected. Items in ...
23 views

### Extending the Knapsack Problem - Value of complementary items

I'm looking for literature related to the following combinatorial optimization problem, which can be generalized to other applications too. I'm wondering what people's thoughts are on how to approach ...
125 views

### Minimize a sum with a weight constraint

We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$. $M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$ ... $M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$ ...
94 views

### Analysis of the following integer program

So the knapsack problem has an integer programming formulation as follows, $$\max_x v\cdot x\\s.t \\x_i \in \{0,1\}\\w\cdot x \leq C$$ Now consider the second integer program which might be a ...
796 views

### Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
69 views

### Problem related to the Knapsack problem: Is it NP-hard?

I am trying to know whether the following problem is NP-hard: Input: A positive number $k$ and $N$ pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
141 views

### Use dynamic programming to find a subset of numbers whose sum is closest to given number M

Given a set $A$ of $n$ positive integers $a_1, a_2,\ldots, a_n$ and another positive integer $M$, I'm going to find a subset of numbers of $A$ whose sum is closest to $M$. In other words, I'm trying ...
98 views

### Optimizing NFL draft picks

I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, ...
55 views

### Aprroximation scheme for Multiple Choice Knapsack

In the paper FAST APPROXIMATION ALGORITHMS FOR KNAPSACK PROBLEMS (E Lawler 1979) gives a FPTA( Fully Polynomial time Approximation ) for multiple choice knapsack problem(MKP) . But MKP being strongly ...
104 views

### Counting the solutions to a restricted 0-1 knapsack problem

Consider the counting knapsack problem $\mathsf{\#IDKNAP}$ : Input: $n \in \mathbb{Z_+}$, $s \in \mathbb{Q}_+$, where $s$ is represented by a fraction $\frac{p}{q}$ in its lowest terms. Output: ...
45 views

### Knapsack Variation (Fixed amount, different types)

I'm trying to figure out a variation to the knapsack problem. The major difference is all objects have a type. For an example we can call them type A, B, C, D, and E. In addition to this we have to ...
57 views

### Are there any algorithms to find top N possible knapsacks?

The classic knapsack problem is maximize $P^T X$ subject to $W^T X\le M$ for $P, W\in \mathbb{R}^d$ and $M\in \mathbb{R}$ and $X\in \{0, 1\}^d$. Is there any research into algorithms that find the top ...
150 views

### 2 Dimensional Subset Sum: looking for information

I do not know if this problems exists with a different name, if it is, I could not find it. The problem is this: Given a set $S$ of $n$ points in $\mathbb{Z}^2$, is there a subset $A\subset S$ ...
158 views

### Finding the n-best items in a 0/1 Knapsack

I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares LÃ³pez in this answer: ...
78 views

### The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? ...
118 views

### How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
54 views

### How to make the standard DP algorithm for 0/1 Knapsack make larger steps?

The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution. Is there any approach to the knapsack problem that does not require ...
151 views

### Find 8 numbers whose sum is closest to a defined value

I have a file that has a number (a positive integer) on each row. Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible. So, ...
32 views

### Algorithms for keeping number of backups constant

The problem is quite simple: backups are done at regular time intervals (with possible but rare exceptions). The storage however is not unlimited, and only a certain number of backups can be stored, ...
81 views

173 views

### Dynamic programming for counting knapsack solutions

Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
76 views

### Heuristics and libraries for the knapsack problem

A student of mine is studying the knapsack problem (0-1 with a single objective). She is also talking to an industry partner who has realistic problems she can try solving (between 1000 to 10000 items)...
41 views

### Spandex knapsack?

I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple ...
90 views

### Complexity of a knapsack variant

Consider the following traditional integer knapsack problem: $\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$ Now ...
48 views

### Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem

I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is ...
128 views

### Output of well-known algorithms for the Subset sum problem

According to Wikipedia: In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is ...