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
11 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
30 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
37 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
40 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
58 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
52 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
0answers
44 views

Get the maximum sum of n items below a threshold

Consider a modified Knapsack Problem where: The number of items to be included is fixed. The value of each item is equal to its weight. Therefore, given a set of numbers, a threshold and the number ...
0
votes
1answer
37 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 ...
1
vote
1answer
24 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
44 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
74 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
45 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
194 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(...
0
votes
0answers
32 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
30 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
64 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
37 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
40 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
207 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
18 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
23 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
62 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
341 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
110 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
140 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
107 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
36 views

Knapsack Problem: Understanding the working

I am reading about KnapSack problem from the following link1: Example of a KnapSack Problem ...
2
votes
0answers
96 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
47 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
56 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
306 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
115 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
424 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
45 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
109 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
64 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
273 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\}$...
3
votes
4answers
126 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
65 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 ...
1
vote
0answers
40 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-...
2
votes
0answers
29 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
794 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
58 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
33 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
33 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
83 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
28 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
2 3 4 5