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
1 vote
0 answers
13 views

Algorithm question (Similar to Knapsack but with an order, or Stock Buy Sell with a cost parameter)

Given : Profit[n]: a n item array indicating the profit on a day (may be positive or negative) Cost[n]: a n item array indicating the cost of holding a stock on a day (always positive) Task: Find $1 ...
Chinmay The Math Guy's user avatar
0 votes
0 answers
23 views

Maximum density knapsack with initial volume and constraint on number of items

Given $\{\rho_i,v_i\}_{i=1}^N$, the densities and volumes of $N$ items, and $K\in \mathbb{Z}_+$. Let $v_0=1$ be the initial volume, and the initial mass is zero. The values $\rho_i,v_i\in \mathbb{R}_+$...
user1000039's user avatar
2 votes
1 answer
94 views

Determining whether two special variants of knapsack have the same optimal value

Given two unbounded knapsack instances, $K_1 = (W_1, weights, values), K_2 = (W_2, weights, values)$, where $W_1 \ne W_2$, what is the complexity of determining $v(K_1) = v(K_2)$ where $v$ returns the ...
rossignol's user avatar
0 votes
0 answers
24 views

Algorithm for Minimum Subset Sum Greater Than K While Minimizing Subset Size

Given an array of positive integers and a positive integer K, I need to find the minimum subset sum S greater than K, and the size of the smallest subset that sums to S. I have attempted to first find ...
mertvy's user avatar
  • 1
1 vote
1 answer
49 views

Knapsack Problem: Find Top-K Lower Profit Solutions

In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table": ...
slaw's user avatar
  • 111
1 vote
1 answer
43 views

Can PTAS be used to optimally solve Knapsack?

Suppose you have a Knapsack (optimisation) problem with integer values and weights, and you know the optimal value $OPT$. Can you compute an optimal solution in polynomial time by using a PTAS or ...
J. Schmidt's user avatar
1 vote
0 answers
66 views

Minimizing leftover items in a 0/1 knapsack problem

I recently asked a question on Stack Overflow and found that I need to solve a 0/1 knapsack problem. However, the problem has evolved to one where the knapsack problem is only part of it. The problem ...
Mohammadreza Khoshbin's user avatar
2 votes
0 answers
113 views

Finding highest value/weight ratio in dependency graph: NP-hard?

I have the following problem, and would like to figure out whether or not it's NP-hard - primarily to know that searching for a polynomial algorithm for it is futile. Approximations are possible, and ...
Pieter Wuille's user avatar
2 votes
1 answer
23 views

Generate paths of fixed length across a weighted matrix (defined in $\mathbb{R}$) whose weights' sum falls into given interval

PSSM or PWM (Positional Weighted Matrix) is a common thing in biological science, used often to observe the distribution of letters inside a group of strings of the same length. It's composed by log-...
Shred's user avatar
  • 121
1 vote
0 answers
23 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}, ...
blackdra_gon's user avatar
0 votes
0 answers
35 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,...
lafinur's user avatar
  • 181
1 vote
0 answers
39 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: ...
adib's user avatar
  • 111
3 votes
2 answers
659 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 ...
Grigori's user avatar
  • 105
3 votes
1 answer
108 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$ ...
user57012's user avatar
  • 105
1 vote
0 answers
62 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 ...
Pablo Messina's user avatar
1 vote
1 answer
39 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 ...
user57012's user avatar
  • 105
0 votes
0 answers
39 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.
Soroush Vahidi's user avatar
1 vote
1 answer
163 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 ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
58 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 ...
pcko1's user avatar
  • 115
0 votes
1 answer
37 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,...
second_and_third_breakfast's user avatar
0 votes
1 answer
113 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 ...
joachimkristensen's user avatar
1 vote
0 answers
70 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 ...
ILIRKI's user avatar
  • 11
1 vote
1 answer
98 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 ...
matkins's user avatar
  • 113
0 votes
1 answer
252 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 ...
talopl's user avatar
  • 101
0 votes
0 answers
173 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 (...
Niraj Jain's user avatar
1 vote
1 answer
599 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 ...
Liopan's user avatar
  • 13
1 vote
2 answers
538 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 ...
boulayo's user avatar
  • 11
-1 votes
1 answer
210 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 ...
nick shetty's user avatar
1 vote
0 answers
103 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\...
Rando5's user avatar
  • 163
0 votes
1 answer
76 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 > ...
in_question's user avatar
0 votes
1 answer
963 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 ...
MMMORG's user avatar
  • 1
0 votes
0 answers
175 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.
Deqing's user avatar
  • 101
1 vote
0 answers
196 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-...
Carpet4's user avatar
  • 111
1 vote
0 answers
101 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$....
super.t's user avatar
  • 123
1 vote
0 answers
276 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 ...
Thang Tran's user avatar
2 votes
1 answer
76 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 ...
Joonazan's user avatar
  • 123
1 vote
1 answer
275 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 ...
Jeffrey's user avatar
  • 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 ...
George Polevoy's user avatar
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 ...
DomainFlag's user avatar
2 votes
1 answer
121 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 ...
erefewinter's user avatar
2 votes
1 answer
634 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 ...
Makogan's user avatar
  • 341
0 votes
0 answers
152 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$ ...
JoshHalas's user avatar
  • 203
3 votes
1 answer
140 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?
Chi Pong's user avatar
2 votes
0 answers
43 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.'s user avatar
  • 159k
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 ...
John19's user avatar
  • 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 ...
kiv's user avatar
  • 339
0 votes
0 answers
155 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 ...
0xAlon's user avatar
  • 15
0 votes
1 answer
425 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 ...
Nikita's user avatar
  • 1
1 vote
1 answer
451 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 ...
Soumya Pattanayak's user avatar
1 vote
0 answers
224 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 ...
Chris Costa's user avatar

1
2 3 4 5 6