Skip to main content

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 votes
1 answer
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 ...
Гого Зукед's user avatar
0 votes
0 answers
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 ...
Dont worry's user avatar
0 votes
1 answer
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 ...
Erotemic's user avatar
  • 123
1 vote
0 answers
16 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
29 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
31 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
59 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
47 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
80 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
124 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
25 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
36 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
  • 195
1 vote
0 answers
40 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
665 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
109 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
65 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
43 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
41 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
180 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
59 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
40 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
125 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
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 ...
ILIRKI's user avatar
  • 11
1 vote
1 answer
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 ...
matkins's user avatar
  • 113
0 votes
1 answer
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 ...
talopl's user avatar
  • 101
0 votes
0 answers
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 (...
Niraj Jain's user avatar
1 vote
1 answer
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 ...
Liopan's user avatar
  • 13
1 vote
2 answers
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 ...
boulayo's user avatar
  • 11
-1 votes
1 answer
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 ...
nick shetty's user avatar
1 vote
0 answers
119 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
82 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
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 ...
MMMORG's user avatar
  • 1
0 votes
0 answers
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.
Deqing's user avatar
  • 101
1 vote
0 answers
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-...
Carpet4's user avatar
  • 111
1 vote
0 answers
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$....
super.t's user avatar
  • 123
1 vote
0 answers
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 ...
Thang Tran's user avatar
2 votes
1 answer
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 ...
Joonazan's user avatar
  • 123
1 vote
1 answer
307 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
132 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
688 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
163 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
145 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
44 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
  • 162k
0 votes
0 answers
126 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
2k 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
169 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

1
2 3 4 5 6