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

239 questions
Filter by
Sorted by
Tagged with
35 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
40 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
80 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
42 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
24 views

417 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 ...
22 views

### Knapsack problem with fractional weights

I was thinking about whether there is a polynomial solution for a knapsack problem with fractional weights. For example, your goal is to maximize the total value of the items subject to the ...
64 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
61 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
58 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
81 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 ...
• 101
52 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
90 views

• 111
1 vote
50 views

### Transforming a multidimensional 0-1 knapsack problem to a maximum weighted clique problem

Just out of theoretical curiosity, is there a way to transform a 0-1 multimensional knapsack problem to a maximum clique problem? Or maybe even easier, to a maximum weighted clique problem (the ...
• 415
51 views

### Combinatorial optimization algorithm with constraints and objective function

I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function. .e.g Say each ...
• 103
3k views

### How to prove that the subset sum problem is polynomially reducible to the knapsack problem

I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete. There are two parts to showing knapsack is NP-...
1 vote
52 views

### Get $n^{\mathrm{th}}$ element of sorted subset sums

I have a sorted multiset (size < 100, real valued) and want to determine the $n^{\mathrm{th}}$ largest of all possible subset sums (including multiplicity in the sums). Attempt at solving : I have ...
1 vote
17 views

### Creating neighbours of solutions to binary knapsack instances

I am currently trying to implement a Tabu Search algorithm for the binary knapsack problem. Part of my goal is to have a variety of different configurations of attributes used and stopping conditions. ...
1 vote
26 views

### Optimal way to pack items with multidimensional weight such that the number of items is minimized?

I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, ...
• 13
18 views

65 views

### Optimal Selection of Non-Overlapping Jobs

I'm trying to find what the family of problem is - as well as an approach - for the following: I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri. Each task ...
• 121
176 views

### Knapsack problem with a constraint

I am familiar with 0/1 knapsack problem. But if the following constraint is imposed... how do I solve the question? If you choose some item 'U' you won't be able to choose another item 'V'. For ...
• 3
162 views

### Dynamic Programming - Thief Variation Probem

I've encountered a Dynamic Programming problem which is a variation of the thief one. Say you are a thief and you are given a number of houses in a row you should rob : House_1,House_2 \dots ...
• 133
1 vote
51 views

### Find the n best choices while maximizing value

Given: A list of slots (A, B, C, ...) Every slots supports a list of choices (C0, C1, C2, C3...) Every choice has a value All slots must be filled with at most n different choices. The sum of the ...
• 121
577 views

### How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?

I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? ...
1 vote
36 views

• 153