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

Fractional knapsack with setup costs

I am considering a variant of the classical fractional knapsack problem, it's written in the following integer programming form Here $v_i, c_i, w_i, b$ are all positive. $c_i$ can be interpreted as ...
0
votes
0answers
24 views

Alternate Knapsack Implementation

I came across a question that requires an alternate implementation converse to the normal Knapsack which is based on a 0-1 logic of considering whether or not to consider an item for the optimal ...
5
votes
2answers
55 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
31 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
30 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
41 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/...
0
votes
0answers
16 views

Solving the multiple-choice knapsack problem for large input

I need to solve the multiple-choice knapsack problem for a very large input size ($\approx 10,000,000$). What is best way to practically do this? I've seen some papers describing FPTAS (=Fully ...
1
vote
1answer
21 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
44 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
32 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-...
1
vote
1answer
123 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
103 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
134 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
77 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 ...
0
votes
0answers
33 views

Knapsack Problem: Understanding the working

I am reading about KnapSack problem from the following link1: Example of a KnapSack Problem ...
2
votes
0answers
91 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-...
2
votes
1answer
37 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. ...
0
votes
0answers
50 views

A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $ T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
0
votes
1answer
177 views

0-1 knapsack problem with minimum and maximum weight capacity

In classical 0-1 knapsack problem we have maximum allowed value for the weight - weight capacity. Let's restrict total knapsack weight by min and max values $$ M \leq \sum_{i=1}^{n}{w_i x_i} \leq W $...
3
votes
0answers
87 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 ...
2
votes
2answers
309 views

Knapsack with a fixed number of weights

Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There ...
2
votes
1answer
41 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 ...
2
votes
0answers
37 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
1answer
86 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 ...
0
votes
1answer
52 views

Knapsack up to the heaviest item

There are $n$ items with weights $w_1,\ldots,w_n$ and values $v_1,\ldots,v_n$. There is a knapsack with capacity $W$. A subset of items is called feasible up to heaviest item if, once the heaviest ...
2
votes
2answers
227 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\}$...
0
votes
0answers
27 views

Knapsack Problem Via Column Generation

If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
3
votes
4answers
109 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 ...
1
vote
1answer
63 views

packing with time-variant weights

This appears to be a knapsack / bin-packing problem, but I seem to have got stuck and could appreciate contributions. Scenario 1: Tough (for me!) There is a one day conference with a set of (4 or ...
0
votes
0answers
18 views

Selecting right cartons for meeting demand (retail supply chain)

I am working on an inventory allocation problem and I could use some help figuring out an optimal solution. Let's say a retail chain's warehouse stores inventory in cartons (physical boxes). Each ...
1
vote
0answers
38 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
17 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 ...
0
votes
0answers
65 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
28 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
575 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
51 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
30 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
32 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
71 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
27 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 ...
2
votes
1answer
44 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
35 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
203 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 ...
2
votes
3answers
934 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
49 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 ...
1
vote
1answer
59 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
138 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
91 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
2 3 4 5