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

265 questions
Filter by
Sorted by
Tagged with
22 views

### Knapsack problem with at least 1 item of two categories, no boundary on total items, unique items

Let's say we want to maximize the caloric intake of a person. One person MUST pick AT LEAST ONE steak and AT LEAST ONE vegetable (no limit of how many steaks or veggies he can pick, as long as they ...
11 views

### Is there a W(1)-hard paremeter for Knapsack?

I am currently working on a parameterized reduction from the Knapsack problem to demonstrate that a particular problem is non-FPT. Specifically, I hope to show that the Knapsack or Resource ...
26 views

### Is this knapsack variant named / studied? "Online algorithm for farthest-from-previous index"

Problem Statement: Given: an ordered list of N items, which we can refer to by index: [0, N). Goal: Write an algorithm to ...
• 123
1 vote
16 views

36 views

1 vote
79 views

### New Knapsack Problem solution with neural network approach

While I was learning the Constraint Satisfaction Problems, I analyzed the Knapsack problem(https://www.csplib.org/Problems/prob133/) and I saw the approach with the neural network was not the best ...
• 11
1 vote
103 views

### Ordered open-end knapsack problem optimised for minimum weight range

Given a fixed number of infinite-capacity containers and a list of items of varying weights, how can I best place the items into the containers preserving their original order in a way that minimises ...
• 113
288 views

### Finding number of combinations of numbers from multiple arrays that add up to a given value

Let $A$ be an array of $n$ integer arrays with unknown lengths and $s \in \mathbb{Z}$ a given number. I want to find the number of combinations of numbers from each array, such that their sum ...
• 101
189 views

### Complexity of fractional knapsack problem

I am bit confused while reading a standard textbook of my curriculum, where it is mention time complexity for knapsack problem is O(nlogn), and rationale they provided is we need O(n) to calculate (...
1 vote
723 views

### Finding optimal combination with multiple constraints

I'm trying to find an optimal combination of players given certain constraints. There are ~300 players. 10 players has to be chosen in the combination. Each player has an assigned value. The goal is ...
• 13
1 vote
627 views

### Variant of the Knapsack Problem 0-1 - One item from each set and zero-weighted items

I understand the basics of the 0-1 problem and its solution. I have a variant of it that I'm trying to solve in a decent way and I'm struggling on it, mostly because of the 0-weighted items. These are ...
• 11
229 views

### Modified knapsack problem with multiple boxes to choose from

I have seen the solution to the knapsack problem and understand it. But I am trying to come up with a dynamic programming solution to the following problem, which is a modified a version of the ...
1 vote
119 views

1k views

### Solve modified knapsack problem using dynamic programming

I'm trying to solve following modified knapsack problem using dynamic programming. What we know: Total number of items Item weight, value and type Knapsack capacity Aims Find Maximum weight of ...
192 views

### Knapsack Problem with exact required item number constraint with no values

Similar to this question but items don't have value $v$. Max weight $W$, every item has weight $w$, must add exactly $L$ items to the knapsack, need to get max weight as possible.
• 101
1 vote
217 views

### combination of traveling salesman with knapsack

I am trying to create an optimisation process for a variant of the travelling salesman problem which is combined with a knapsack problem in the following way: Let there be a set of points $P$ on a two-...
• 111
1 vote
104 views

### Proof for knapsack with unlimited items

This is the knapsack problem where the items are unlimited. Let $K(w)$ be be the maximum value achievable for the knapsack capacity of $w$, and $w_i$ and $v_i$ are the weight and value of the item $i$....
• 123
1 vote
284 views

### Is Knapsack-optimization problem NP-hard while Knapsack-search problem NP-complete?

I am learning Computational Complexity. Is Knapsack-optimization problem (find an arrangement to maximize the value) known to be NP-hard, while Knapsack-search problem (find an arrangement so that ...
• 111
83 views

### Nonlinear Knapsack with small integer weights

I have a problem that looks like a 0-1 Knapsack problem, except that the value of each item is a vector of length about 5, $v=(v_1,\dots,v_5)$. I want to maximize the product of components of the sum ...
• 123
1 vote