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
0answers
18 views

Proving Correctness of Knapscap Fraction Algorithm

I am trying to prove correctness of Knapsack algorithm below: Algorithm works by taking rations of values of items to weights and then sort them in decreasing order taking $O(n\log{n})$ time. So to ...
1
vote
1answer
27 views

Knapsack like problem with nonnegative weight constraint

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 ...
0
votes
1answer
12 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 ...
0
votes
0answers
26 views

A Variant to "Boats to Save People"

This question is a variant of LeetCode 881. Boats to Save People by removing the restriction of "each boat carries at most two people at the same time" from the original question. Problem ...
1
vote
0answers
85 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
1answer
29 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 ...
1
vote
1answer
52 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 ...
0
votes
0answers
80 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$ ...
3
votes
1answer
55 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
0answers
36 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 ...
0
votes
0answers
86 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 ...
3
votes
1answer
106 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 ...
0
votes
0answers
45 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 ...
0
votes
1answer
115 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
vote
1answer
112 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
0answers
82 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
1answer
54 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}$. ...
1
vote
1answer
56 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 $\...
1
vote
0answers
36 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
1answer
36 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 ...
0
votes
1answer
639 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
0answers
51 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 ...
0
votes
0answers
83 views

0/1 Knapsack problem. How does the total weight does not exceed the limit?

I am trying to wrap my head around the knapsack problem algorithm. I understood the most of it except one tiny thing. On the left is the [val,weight] and on the ...
1
vote
0answers
9 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
1answer
22 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, ...
0
votes
1answer
15 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 = \...
1
vote
2answers
109 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 ...
2
votes
1answer
144 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 ...
2
votes
0answers
51 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
1answer
128 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
1answer
55 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 ...
0
votes
1answer
155 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
1answer
43 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
1answer
83 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
votes
1answer
127 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
1answer
47 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 ...
0
votes
1answer
450 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
0answers
29 views

How to the NP hard of a problem that search for a subset of points with maximum scores?

Suppose in a plane, there is a set of points, whose distance to $(0,0)$ is always 1: $[(0,1),(1,0),(0.707,0.707),(0.707,-0.707),...]$ Each point is assigned with a weight (possible negative): $[w(...
5
votes
2answers
106 views

Detecting conservation, loss, or gain in a crafting game with items and recipes

Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\...
0
votes
1answer
70 views

Why is a Knapsack problem not an LP problem?

We know that LP can solve optimization problems that have linear constraints and linear objective functions. A knapsack problem can be formulated into a linear objective function (because it is just ...
0
votes
0answers
57 views

Why is "encoding" important in time complexity?

I read many writing about the time complexity of 0-1 knapsack problem. (https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668) In conclusion, the ...
1
vote
1answer
354 views

0-1 knapsack without repetition

My question is why O(nW) at the knapsack problem is pseudo-polynomial. I read lots of the explanation at stackoverflow, But I don't really understand it. (https://stackoverflow.com/questions/19647658/...
1
vote
1answer
24 views

Knapsack dynamic programming complexity issue for $W=1$, is it $O(n)$?

The 0-1 knapsack problem is given by $$\begin{align}&\text{maximize } \sum_{i=1}^n v_ix_i,\tag{P1}\\& \text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{...
1
vote
0answers
47 views

Looking for an algorithm or similar mathematical problem for trading ownerships in shared property

Suppose there is $N$ property. Each property is owned by multiple person. (they have shared ownership) For example: $Person_1$ owns 22% of $Property_1$, $Person_2$ owns 35% of $Property_1$ and $...
0
votes
0answers
126 views

Maximum-density multiple-choice knapsack problem

I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-...
2
votes
1answer
1k views

Knapsack Problem with exact required item number constraint

How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight ...
2
votes
1answer
125 views

Knapsack-like problem with profit formula

Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once. The ...
2
votes
2answers
152 views

Distribution Optimization Algorithm

I'm trying to classify and come up with a reasonable solution for the following problem (abstracted from a real world problem). Problem Imagine StackOverflow started offering a subscription where ...
1
vote
2answers
235 views

Proof by contradiction for greedy algorithms

I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never ...
2
votes
0answers
119 views

PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

Consider the following problem: We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...

1
2 3 4 5