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

Algorithms of placing N weighted balls into M uniform bins while striving for balanced weight?

Suppose there're $N$ weighted balls and $M$ equal weight bins, it's guaranteed at least one placement exists that all the balls can be placed into bins. What's the right algorithm to achieve a well-...
0
votes
0answers
9 views

Algorithmic question: distribute balls, optimise for balancing (i) weights (ii) probabilities of picking balls

I have an algorithmic problem that requires some lengthy explanation, which follows below. tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the ...
-1
votes
0answers
13 views

How to select M max Sum from N stack

We are given N stacks of variable length. We need to choose M element such that sum is maximum. example 3 3 stack a) 1 2 200 stack b) 5 10 7 stack c) 4 6 the answer will be 1+2+200 = 203 .
0
votes
0answers
17 views

Solving sequential multi-knapsack problem

Suppose I have $n$ items, each with value $v(j)$ and weight $w(j)$, and $m$ knapsacks each with capacity $c(i)$. If I make the assumption that $w(j-1)$ evenly divides $w(j)$, then there's a nice ...
2
votes
0answers
21 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: ...
2
votes
0answers
24 views

Knapsack problem in real life

My task is to develop an algorithm for the optimal arrangement of cylindrical objects in cartons. The algorithm is to have the task of placing as many products as possible into cartons, at the same ...
1
vote
0answers
16 views

TSP with knapsack combo

My problem statement is that my agent has to visit multiple pickup points once to collect orders, say Item A, Item B, Item C...... etc. We are using TSP for that. Now say Item A are stored in 3 ...
2
votes
0answers
23 views

Knapsack problem with specified amount of objects

Suppose I need exactly $X$ flowerpots. I have $Y$ flowerpots to choose from, and $Y > X$. Each of the $Y$ flowerpots has a cost and a capacity. I have a fixed budget to buy flowerpots. The ...
1
vote
1answer
27 views

Relaxation of the knapsack constraints

A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$. I have a set of points defined as the knapsack constraint $$ \mathcal{X} = \{x \in \...
4
votes
1answer
57 views

Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution

All the explanations for why the $O(nW)$ DP algorithm that solves the Knapsack Problem is NOT polynomial repeat the same thing: it is the length (in bits) of the input that matters, not its value/...
1
vote
1answer
24 views

How to put elements in allowed bags?

Let's say I have a list of "Items" I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag. I want to place ...
1
vote
1answer
31 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)$, ...
3
votes
1answer
30 views

Non-existence of approximation algorithm for the knapsack problem

I am working on the following exercise: Prove that if $P \neq NP$, there cannot exist an approximation algorithm $A$ for the knapsack problem (KP) such that $\exists k \in \mathbb{N}, \forall I \in S: ...
1
vote
1answer
74 views

Multiple knapsack problem with equal profit and different weight

I am doing a research about the load balancing problem in 5G system, but I am not sure if my problem is a NP-complete problem. The problem is: given a set of n items and a set of m knapsack capacity ...
0
votes
0answers
15 views

Knapsack problem understanding a question

I don't understand this question and I would really appreciate it if someone could help. So it starts off with explaining the Knapsack Problem then it asks me to write a function that calculates the ...
1
vote
3answers
106 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 ...
2
votes
1answer
34 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 ...
0
votes
0answers
15 views

Why does the knapsack dynamic programming solution has runtime of O(nW)? [duplicate]

Can you please help me analyse the runtime of the knapsack dynamic programming (which i have seen somewhere is O(nW))? This is the algorithm i an using: Define M[i,s] to be the maximum value that ...
1
vote
1answer
50 views

How to count the combinations not greater than a given volume in a knapsack problem?

You are given a certain set of items with weight wi and the volume of the bag. Case: ...
0
votes
1answer
104 views

Modified Knapsack Problem

I have a problem with the following optimisation problem: In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, ...
2
votes
1answer
62 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 ...
2
votes
3answers
153 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 ...
3
votes
0answers
33 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 ...
1
vote
1answer
52 views

Algorithm for modified knapsack problem

We have $n$-players in a game. We have a population of players we can choose from. Each player score is a normally distributed random variable and each player has a cost to add to the team. We are ...
0
votes
0answers
32 views

Multi-dimensional knapsack

Consider a multidimensional knapsack problem, and let $M$ denote the number of knapsack constraints. I am trying to solve a problem where $M$ is exponential in the number of $0-1$ variables in my ...
0
votes
0answers
52 views

Knapsack approximation algorithm (weights scaling)

I am trying to prove the following Knapsack approximation algorithm, the problem definition: Input: A set $S$ of $n$ objects that contains weights and values: $w_1,w_2,\ldots,w_n$ (weights) $...
1
vote
0answers
79 views

Closest Value instead of Max Value in Knapsack problem

I have a problem like the knapsack problem, except instead of finding the max value, I'm trying to find the closest value to a given value. Anyone know where to start, have a name for this problem, ...
0
votes
0answers
153 views

Multiple Knapsack Problem, but with exact weight/capacity? (All knapsacks have to be filled completely)

I have a few knapsacks of given capacities. Also, much more items of given weights and values. As usual, items have to be put into knapsacks to maximize profit. What is different from a standard ...
0
votes
0answers
47 views

Multi Knapsack each with different constraints

It seems that there's no end to knapsack variations… here's the one I bumped into (at work): There are: N items, each with the usual value and weight properties. M bins, each with an upper ...
1
vote
2answers
344 views

What's the time complexity bound for the Knapsack with real weights?

Let's start with the formalism: Let $W$ be the total weight of our bag, $1,...,n$ be our elements, $w_1,...,w_n$ their corresponding weights, and $v_1,...,v_n$ their corresponding values. As is ...
2
votes
1answer
332 views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
0
votes
1answer
63 views

Oven cooking queue problem: need help to determine its nature

CS community! I'm more of a practical programmer than a computer scientist, so I need your help to find a solution (or at least point me into the right direction) to an extremely practical problem ...
1
vote
1answer
115 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
1
vote
1answer
157 views

Help writing a dynamic programming algorithm in English

It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....
1
vote
2answers
431 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 ...
1
vote
2answers
167 views

Variant of the Knapsack Problem

I've got problem on integer programming, specifically with the following knapsack problem. I'd be happy to get some suggestions on how to solve the problem in a time efficient way. There are 120 ...
1
vote
0answers
46 views

Calculate maximum sum of nodes property with limit on distance being traversed between nodes in a given graph

Given is an undirected weighted graph with N nodes, with each node having a property/Value. Aim is to find the bestpath which maximizes the sum of the nodes property which can be visited given a ...
1
vote
1answer
56 views

Knapsack-type problem where the objective function is a ratio

I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole ...
5
votes
0answers
80 views

Specific quadratic 0-1 knapsack problem solvable in linear time?

I am interested in a simple variant of the quadratic knapsack problem. Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
2
votes
2answers
2k views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
1
vote
1answer
32 views

How do I model this expression maximization problem as a Knapsack problem?

Given two arrays of the same length $n$: $A = \{a_1,a_2,\dots,a_n\}$, $B = \{b_1,b_2,\dots,b_n\}$, I have to maximize the following expression: $$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}...
-1
votes
1answer
86 views

A question about a variant of a knapsack problem

I have the following problem: Let $q_1,\cdots,q_k$ be natural numbers $> 0$, $q := \sum_{1\le i \le k}{q_i}$ and $s_1,\cdots,s_k$ be positive $>0$ real numbers, and $S$ be a positive real number....
1
vote
0answers
46 views

Knapsack problem with additional conditions for data objects

I've been trying to theorize how to solve a certain type of problem for months now. Suppose you have a collection of $m$ pre-defined $(d+2)$-dimensional vectors like so: $$(v, s, m_1, \dots, m_{d})$$...
1
vote
1answer
568 views

Fantasy premier league dream team algorithm?

For those of you who are not familiar with FPL, here's a short version. You have players playing as either Goalkeeper, Defender, Midfielder or Forward. Each player has some price (either rounded to .5 ...
1
vote
3answers
87 views

Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?

Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ ...
0
votes
1answer
534 views

proof of correctness for greedy knapsack algorithm

I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement ...
1
vote
0answers
319 views

why knapsack problem is a NP complete?

I understand that knapsack problem is solved with dynamic programming in O(nW) time which is not polynomial but there is a greedy solution for knapsack problem which solves it with O(nLgn) time so how ...
1
vote
1answer
228 views

Relative order of values and weights in Knapsack

In knapsack problem, we have some items with some values and weights. We also have a knapsack with a specific capacity, and we intend to fill the knapsack with these items. The main objective of this ...
1
vote
2answers
250 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 ...
2
votes
1answer
690 views

A Special Case of Multiple Choice Knapsack Problem: Is it NP-hard?

The multiple choice knapsack problem (MCKP) can be defined as follows: MCKP is known to be NP-hard in general. I have a special case of MCKP for which $N_i=\{1,2,\cdots,|N_i|\}$, for all $1\...