# Questions tagged [knapsack-problems]

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.

219 questions
Filter by
Sorted by
Tagged with
520 views

### Solving a Rod Cutting Problem

I'm trying to come up with an algorithm for optimizing cutting a rod. Most of the examples I see online are for a stock of rod of a single length and optimizing the way to cut it up for max price. I ...
451 views

### Knapsack Problem with Vector Values

I am searching for information on a variant of the 0-1 Knapsack Problem I will call the Vector Knapsack Problem (VKP), which is basically the same as the standard KP except that the values being ...
161 views

### Can the standard knapsack problem be solved using LLL?

It is well-known that the Merkle–Hellman knapsack cryptosystem can be solved using the LLL algorithm. In the Merkle-Hellman knapsack cryptosystem, we're trying to find a solution $x_i \in \{0,1\}$ ...
81 views

### Does dynamic programming always add one item per sub-solution?

In the 0-1 knapsack problem, I am given a set of items with their weights and the weight that a knapsack can carry. The objective is to maximize the number of items I can carry subject to the fact ...
422 views

### Modification of dynamic programming for a knapsack problem

We have the following recursive function for the dynamic programming problem for a knapsack problem: \begin{align} V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \...
3k views

### Variation of knapsack problem

I have a menu of n items, with each item having a value. Given the total amount spent, I have to figure out all the possible combinations of items purchased. Example, I have three menu items: item 1: ...
154 views

### Matching 2 sets of items by price

I'm trying to solve the following problem in the most efficient way I can find. I want to trade my items for someone elses items, every item have a price and a value. I want to maximize the value of ...
513 views

### What are some concrete (near-)“worst-case” examples of subset-sum?

I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively. I'm measuring its performance by the average amount of time taken per subset found. However, I suspect ...
92 views

### Getting output of dynamic programming, (contiguous sub array, box stacking)

I am attempting to output the largest stack of boxes given an input of a set of boxes. Currently I have an array called maxWeight that has the values of the boxes sorted from largest to smallest, this ...
110 views

2k views

### Multi- Knapsack problem variation

I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each ...
275 views

### Is a Knapsack Problem with only Color Constraints NP-Complete?

I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors. There exists a constraint on ...
143 views

263 views

### Subset sum with wider constraint

The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$: $max \displaystyle\sum_{i} x_i, x_i \in \{0,1\}$ subject to $\displaystyle\sum_{i} w_ix_i \leq W$ for a ...
64 views

### Help me identify the type of Knapack Problem I am dealing with

I have a multiple knapsack problem I am trying to solve. To get the right solution, we need to ask the right question. My question is simply to identify what type of problem I have, not to solve the ...