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.
262
questions
3
votes
1
answer
1k
views
Optimizing NFL draft picks
I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, ...
- 133
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$ ...
- 105
3
votes
1
answer
104
views
Determine aproximation factor in a greedy algorithm
Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences.
We want to choose a menu such that we minimize the cost and ...
- 89
3
votes
4
answers
296
views
Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people
Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.
The total value of $n$ gifts ...
- 209
3
votes
3
answers
4k
views
0/1 Knapsack problem with real-valued weights
Is there a known solution for the 0/1 knapsack problem that allows the weights of the objects to be real numbers? The only algorithm I can think of is a brute force search. I have tried searching for ...
- 171
3
votes
1
answer
2k
views
Multi- Knapsack problem variation
I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each ...
- 131
3
votes
2
answers
3k
views
Knapsack problem: equal profits
I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal.
More formal definition of the problem from a Wikipedia article on KPs:
If all the profits ...
user95635
3
votes
1
answer
5k
views
Confusion related to time complexity of dynamic programming algorithm for knapsack problem
I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming
I didn't get how the time complexity of the algorithm came out to be $O(nV^...
- 299
3
votes
0
answers
504
views
Finding all feasible solutions to a multiple-knapsack program
How can I find all feasible solutions to a 0-1 integer program that I have based on a knapsack-style problem?
I have $n$ items and $m$ knapsacks. Each knapsack has a space limitation and each item ...
- 31
3
votes
0
answers
278
views
Split a graph into 2 components with known distribution?
I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there ...
- 395
3
votes
0
answers
213
views
Is there a pseudo polynomial time algorithm for this 0-1 quadratic subset sum problem?
Say that we have some (integer) weights $w_{1,1},w_{1,2},...,,w_{m,m}$ and a target sum $W$.
Suppose that we want to find whether there are $a_1,...,a_m \in \{0,1\}$ such that
$$\sum_{i = 1}^{m} \...
- 168
3
votes
0
answers
1k
views
Finding the n-best items in a 0/1 Knapsack
I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: ...
- 131
2
votes
1
answer
494
views
Why there is no FPTAS for multiple knapsack problem for two knapsacks unless P=NP?
The multiple knapsack problem (MKP) is defined in "A PTAS for the Multiple Knapsack Problem" as:
Instance: A pair $(B, S)$ where $B$ is a set of $m$ knapsacks and $S$ is a set of $n$ items. Each bin $...
- 693
2
votes
3
answers
18k
views
Brute force method to solve the 0-1 knapsack problem
I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:
If the brute force ...
- 203
2
votes
1
answer
594
views
Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?
According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
- 213
2
votes
1
answer
1k
views
Subset sum algorithm in O(n³ log n)?
I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers.
After my research, I'm lost between all the algorithms ...
- 151
2
votes
2
answers
201
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 ...
- 135
2
votes
1
answer
2k
views
Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed
I would like to find the sum of values from a given number array, where the repetition of numbers are allowed, closest to a target but the sum cannot exceed the target. If there are more solution, I'd ...
2
votes
1
answer
3k
views
01 Knapsack with selection of items with minimum total weight
I have a slightly modified version of a classical 01 knapsack problem. Specifically, the problem has an additional constraint which requires that if more than one feasible selection with equal value ...
- 155
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-...
- 121
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 ...
- 123
2
votes
2
answers
524
views
How to solve this very complicated assignment problem
A set of m items need to be placed into n stacks, where m > n. Each stack has z positions. An item has different widths when placed into different positions in a stack. The width of an item depends ...
- 21
2
votes
1
answer
695
views
A special case for the subset sum problem
If we wanted to see if any disjointed subset of a set $X = [w_1, ..., w_n]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution ...
- 125
2
votes
1
answer
86
views
Why is OPT at least the most valuable item for FPTAS Knapsack?
In all the presentations of an FPTAS for Knapsack I've seen, it is asserted that the optimal value is at always at least the value of the maximum-valued item (e.g. here, slide 12, where we have $V \...
- 121
2
votes
1
answer
484
views
Output of well-known algorithms for the Subset sum problem
According to Wikipedia:
In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is ...
- 151
2
votes
1
answer
630
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 ...
- 341
2
votes
1
answer
128
views
How to partition a set in order to minimize the number of the elements and their interactions?
Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From ...
- 1,046
2
votes
3
answers
537
views
Modification of dynamic programming for a knapsack problem
We have the following recursive function for the dynamic programming problem for a knapsack problem:
\begin{align}
V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \...
- 45
2
votes
2
answers
8k
views
Multiple Constraint Knapsack Problem Dynamic Programming
Is there any way for solving the Knapsack problem when we are limited by several constraints?
Let's assume that we have a set of items in which we have value v ...
2
votes
1
answer
385
views
Can the unbounded knapsack problem be described as a matrix exponentiation?
It seems that the general approach to a dynamic programming problem is to formulate a recurrence relation and then either implement a top down recursive solution or a bottom up iterative solution.
...
- 121
2
votes
1
answer
2k
views
Ordered knapsack problem?
I'm trying to find the name of this problem, and with it a reasonable algorithmic solution.
Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights $a_1,\...
- 531
2
votes
1
answer
557
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
1
answer
93
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 ...
- 121
2
votes
1
answer
137
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 ...
anon
2
votes
1
answer
160
views
Unbounded, 2-dimensional knapsack problem
I have the following problem:
There is rectangle with fixed $W > w_i$ width and $H > h_i$ height.
Given a set of item types, where each type has some $w_i$ width, $h_i$ height and $v_i$ value.
...
- 21
2
votes
2
answers
826
views
Multiple choice knapsack dynamic programming
Giving a the following:
A list of a store items $T=\{t_1, t_2,...,t_n\}$.
A list of prices of each item $P=\{p_1, p_2,...,p_n\}$.
A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$...
- 35
2
votes
1
answer
87
views
Shrinking Item 0-1 Knapsack problem
I have encountered a variant of the knapsack problem with shrinking items.
Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$, ...
- 121
2
votes
1
answer
156
views
Minimize shipping cost based on weight and price constraints
I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows:
There is a ...
- 21
2
votes
3
answers
368
views
Check if knapsack problem instance is unsolvable
Is it possible to easily check if an instance of the 0-1 knapsack problem is unsolvable? Example: Assign 10 40-min tasks to 8 employees that have 60 minutes available each. Clearly, this instance is ...
- 21
2
votes
1
answer
788
views
Knapsack Problem with Vector Values
I am searching for information on a variant of the 0-1 Knapsack Problem I will call the Vector Knapsack Problem (VKP), which is basically the same as the standard KP except that the values being ...
- 129
2
votes
1
answer
567
views
Approximation scheme for Multiple Choice Knapsack
The paper _Fast Approximation Algorithms for Knapsack Problems (E. Lawler, 1979) gives an FPTAS (fully polynomial time approximation scheme) for the multiple choice knapsack problem (MKP). But ...
- 121
2
votes
1
answer
51
views
Spandex knapsack?
I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple ...
- 143
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 ...
- 31
2
votes
0
answers
112
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 ...
- 121
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 ...
- 123
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.♦
- 159k
2
votes
0
answers
76
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 ...
- 269
2
votes
0
answers
197
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-...
- 113
2
votes
0
answers
42
views
Finding a non negative combination of integers that adds up to a certain number [duplicate]
I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$.
I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that
$$n_1c_1 + n_2c_2 + \dots + ...
2
votes
0
answers
82
views
Selecting objects to maximize value while under multiple constraints
I think it will be best to explain the problem first and then explain what I am thinking:
I have a dataset similar to the following:
...
- 21