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.
255
questions
1
vote
0
answers
18
views
Approximation Algorithm for Bin packing Variant with Packing Overhead
I recently came up with this bin packing variant and was wondering, if someone has studied it before:
Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
- 11
0
votes
0
answers
24
views
Greedy algorithm for trading cryptocurrencies with perfect price information
Assume the following hypothetic scenario:
You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
- 181
1
vote
0
answers
28
views
Grouping transactions having pre-determined sums?
I have a transaction grouping problem that I'm having trouble to devise the algorithm to solve it. Not even ChatGPT (version 3.5) can solve this correctly.
Suppose I have five transactions:
...
- 111
3
votes
2
answers
644
views
Find max total revenue in a directed graph
Problem:
Imagine you are an agent with a knapsack, who travels a known route of cities. All cities are different: $C_1 \rightarrow C_2 \rightarrow \dots \rightarrow C_n$. Each city offers you to buy ...
- 95
3
votes
1
answer
107
views
Knapsack with fixed size and flexible profit
We have $3n$ items with profits $p_1, \dots, p_{3n}$ (sum = $P$) and weights $w_1,\dots,w_{3n}$ (sum
= $W$). We want to determine whether we can choose exactly $n$ items with profit at least $P/2 - 1$ ...
- 95
0
votes
0
answers
43
views
Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights
I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
- 159
1
vote
1
answer
35
views
Knapsack with fixed size
We have $3n$ items with profits $p_1, \dots, p_{3n}$ (sum = $P$) and weights $w_1,\dots,w_{3n}$ (sum
= $W$). We want to determine whether we can choose exactly $n$ items with profit at least $P/2$ and ...
- 95
0
votes
0
answers
32
views
List of weakly NP-HARD problems
I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
1
vote
1
answer
148
views
knapsack with graph connectivity constraints
I am looking for a variant of the knapsack problem in which the items are nodes in an undirected graph, and the knapsack must be filled with a connected subgraph. Formally:
The input is an undirected ...
- 5,730
0
votes
1
answer
56
views
NP-completeness of graph problem
I am studying for my final exams in complexity theory and I came across a graph problem which I cannot fully prove that it is NP-complete. Its gist is the following:
Assume that you have a weighted ...
- 3
0
votes
1
answer
33
views
Is there a non bruteforce apporach to solving a "synergistic knapsack"?
Sorry for making up a name for the thing, the main reason for posting this question is that I can't find out the name of the problem that i'm thinking about.
I was messing around with min/max DP stuff,...
0
votes
1
answer
88
views
Knapsack with no capacity
Given a set $S$, a value function $v(s)$ and a cost function $c(s)$ for all $s \in S$, and integers $B$ and $K$, the classic formulation of the Knapsack problem asks if there is a subset $S' \subseteq ...
0
votes
0
answers
18
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 ...
- 95
1
vote
0
answers
62
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
85
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
97
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 ...
- 305
0
votes
1
answer
131
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
126
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
415
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
425
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
188
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
84
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
59
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 > ...
- 31
0
votes
1
answer
888
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
158
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
159
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
89
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
234
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
2
votes
1
answer
69
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
226
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
26
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 ...
- 103
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 ...
- 111
2
votes
1
answer
91
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 ...
- 23
2
votes
1
answer
564
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 ...
- 331
0
votes
0
answers
144
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
126
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?
- 71
2
votes
0
answers
42
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 ...
D.W.♦
- 156k
0
votes
0
answers
125
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
1k
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
128
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
377
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
406
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
196
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 ...
- 111
1
vote
1
answer
291
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
105
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
56
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 ...
- 457
0
votes
1
answer
85
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
6k
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-...
- 33
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
38
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.
...
