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.
268 questions
1
vote
1
answer
76
views
Simple Unbounded Multi-Knapsack with Distinct Items Constraint - strongly or weakly NP-c?
Is the following Knapsack problem strongly or weakly NP-hard? We have unbounded knapsacks, meaning we can use each item unlimited number of times.
Given:
$I = \{ w_1, ... w_n \}$ - a set of the ...
0
votes
1
answer
82
views
Variation of Knapsack problem that finds minimum value instead
Imagine this variation of the knapsack problem:
Given a set of n items and a container that requires a minimum weight of W, where each item has a weight w and value v, find a set of s items with a ...
1
vote
1
answer
136
views
Knapsack with both upper and lower capacity
In the usual knapsack problem, there are $n$ items with values $v_1,\ldots,v_n$ and costs $c_1,\ldots,c_n$ and a total budget $B$, and the goal is to select a subset of items with maximum total value ...
- 6,087
0
votes
0
answers
179
views
Multiple Knapsack with fixed weight and proprity lists
Let's say that we have
A set of $m$ knapsacks $B = \{ b_1, b_2, ..., b_m\}$
$\forall b_i \in B, \exists c_i$ which is the capacity of the knapsack $b_i$. It's an integer.
A set of $n$ items $I = \{ ...
- 1
-1
votes
1
answer
70
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 ...
0
votes
1
answer
84
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 ...
- 123
1
vote
0
answers
39
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 ...
0
votes
0
answers
59
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}_+$...
- 101
2
votes
1
answer
125
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
1
vote
0
answers
64
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 ...
- 11
1
vote
1
answer
147
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":
...
- 111
1
vote
1
answer
80
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 ...
- 827
1
vote
0
answers
133
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 ...
3
votes
1
answer
212
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 ...
- 151
2
votes
1
answer
67
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