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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
17 views

Does 0 1 knapsack have different bottom up approaches in literature?

Are COTA Vygen 2012 and Algorithms Illuminated Part 4 different ? COTA mentions the table should have items and Weight versus Algorithms Illuminated mentions table should have items and values. I can ...
1 vote
0 answers
43 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
1 answer
69 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
0 votes
0 answers
81 views

Has this problem related to bin-packing and knapsack been studied?

There is a problem I recently encountered in my work which is related to the knapsack and bin packing problems. But I couldn't find the exact problem anywhere. Say you have some suitcases. Each of ...
0 votes
1 answer
75 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
0 votes
0 answers
67 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
1 answer
192 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
2 answers
223 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
-1 votes
1 answer
119 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
0 answers
53 views

Running time of 01-Knapsack-like with negative weight/values, absolute value weight constraint, and volume constraint?

Background In the classic formulation of the knapsack problem with both weight and volume constraints, we are given a collection of $n$ items where item $i$ has weight $w_i\in\mathbb{N}$, volume $u_i\...
  • 163
0 votes
1 answer
43 views

Knapsack with quadratic constraint

Suppose I have a variant of the knapsack problem: $$\max_{x} \sum_{i=1}^n v_ix_i$$ $$(\sum_{i=1}^n w_ix_i - W)^2 \leq k$$ for $v_i, w_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}, k > ...
0 votes
1 answer
645 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 ...
  • 1
0 votes
0 answers
101 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
0 answers
86 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
0 answers
68 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
0 answers
116 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 ...
2 votes
1 answer
62 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
1 answer
149 views

Knapsack like problem with nonnegative weight constraint [closed]

I am dealing with a knapsack-like problem with one difference from the conventional problem: the “weights” can be positive or negative and the constraint is $\sum w_i x_i \ge 0$ instead of $\sum w_i ...
  • 13
0 votes
1 answer
23 views

Calculating minimal discriminator of a set of columns in a matrix with unique rows

Having a matrix $M$, with unique rows, how to calculate a minimal subset of colums $D$ such that every row is unique? Also, how to maximize the amount of unique rows, if the number of chosen columns ...
1 vote
0 answers
91 views

Fixed bin packing for maximizing the number of matches in every bin

Original question: Given a symmetric matrix with matches count between different transcriptions, the objective is to maximize the batches total matches count while minimize the standard deviation ...
2 votes
1 answer
55 views

Random splitting with fixed size range

I ran into this problem while trying to create a procedural texture algorithm. I ended up using a greedy approximation and shuffling it to hide the bias, but I was wondering if there was a way to find ...
2 votes
1 answer
404 views

How do you prove that a solution to the 0-1 knapsack problem is optimal?

Given a boolean vector b representing a solution to the knapsack problem with n elements k capacity and where each element has integer weight and value. Proving that the solution is a solution is ...
  • 143
0 votes
0 answers
113 views

Proving that a problem is not FPT using reduction

In the Inclusive Vertex Cover problem, For a given graph $G=(V,E)$, each vertex $u\in V(G)$ has weight $u_{w} \in \mathbb{N}$ and value $u_{v}\in \mathbb{N}$. The value and weight of a set cover $S$ ...
  • 203
3 votes
1 answer
105 views

FPT algorithm for Knapsack

I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic. Can someone help with a reference?
2 votes
0 answers
41 views

Path that stays within a convex polyhedron

Let $\mathcal{P},\mathcal{Q}$ denote two convex polyhedra in $\mathbb{R}^d$, which can be represented by a set of linear inequalities. Let $A \subset \mathbb{R}^d$ be a finite set of vectors. The ...
  • 150k
0 votes
0 answers
110 views

Algorithm for Variant of 0-1 Knapsack Problem

Variant of 0-1 Knapsack Problem is when you can choose exactly $k$ items from $n$ items, and $k$ is positive integer parameter that came in the input. Is there an algorithm with running time ...
  • 63
4 votes
1 answer
921 views

0/1 knapsack problem: Greedy Algorithm Counterexample

While reading about 0/1 knapsack problem on the Internet, many tutorials considered value/weight ratio to solve the problem and I was wondering will it always contain the element with the greatest ...
  • 339
0 votes
0 answers
94 views

Filling Two Knapsacks with greedy algorithm

I've got the next problem, where I have two, instead of one, knapsacks. Formally, we have items $1, \ldots , n$ and each item $i$ has a positive integer weight $w_i \in \mathbb{N}$ and a positive ...
  • 15
0 votes
1 answer
259 views

How to derive max amount of items from DP table of Knapsack problem?

I have a little bit changed algorithm for 1-0 Knapsack problem. It calculates max count (which we can put to the knapsack) as well. I'm using it to find max subset sum which <= target sum. For ...
  • 1
1 vote
1 answer
339 views

Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own

I had an online round at a company where I was asked this question. There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$. Each item has three ...
1 vote
0 answers
157 views

0/1 Knapsack problem with minimal cost

so i have this problem where: I have to accomplish a challenge A with n quests. Each quest gives me: p points and needs t time to be done. The object is to complete the challenge A that needs M ...
1 vote
1 answer
185 views

How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

I am reading a proof that the Subset Sum decision problem is NP-complete. I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. ...
  • 108
1 vote
1 answer
91 views

How to create a subset with a given length and mean?

I have a set of numbers $P=\{p_1,\dotsc,p_{|P|}\}$, where $|P|$ is the length of the set. I want to select a subset, $S$, from $P$ such that its mean is approximately equal to a predefined value $\...
  • 111
1 vote
0 answers
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 ...
0 votes
1 answer
61 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
1 vote
1 answer
4k 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
0 answers
53 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
0 answers
23 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
1 answer
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
0 votes
1 answer
21 views

Looking for clarity on step in fractional knapsack problem proof

I'm reading through the proof for the fractional knapsack problem presented here: https://www.cs.rice.edu/~nakhleh/COMP182/Knapsack.pdf I follow the proof until the definition of the new set $Q = \...
  • 113
1 vote
2 answers
295 views

About the pseudo polynomial complexity of the KnapSack 0/1 problem

I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some ...
  • 23
2 votes
1 answer
433 views

0-1 Knapsack problem with item discounts

I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included ...
  • 121
2 votes
0 answers
65 views

Partition a set of factors so that the difference between products is minimized

I'm sure this problem must be well-known... Given a collection $S$ of numbers, partition them into exactly two sub-collections, $A$ and $B$ (I mean, by definition $B$ is just $S-A$) such that the ...
0 votes
1 answer
170 views

Knapsack Problem with Constraints on Item Values

Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight ...
0 votes
1 answer
60 views

Distribution of resources from providers to maximum number of receivers

Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what ...
  • 47
0 votes
1 answer
272 views

"Knapsack problem" with repetition, "lesser or equal" constraint, and recording all valid combinations

In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head. Let $x_i$, $ 1\leq ...
2 votes
1 answer
84 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 ...
0 votes
1 answer
223 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
3 votes
1 answer
185 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 ...
1 vote
1 answer
53 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 ...

1
2 3 4 5