# 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.

220 questions
Filter by
Sorted by
Tagged with
1answer
95 views

### How to derive max amount of items from DP table of Knapsack problem?

I have a little bit changed algorithm for 1-0 Knapsack problem. It calculates max count (which we can put to the knapsack) as well. I'm using it to find max subset sum which <= target sum. For ...
1answer
29 views

### Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own

I had an online round at a company where I was asked this question. There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$. Each item has three ...
0answers
46 views

### 0/1 Knapsack problem with minimal cost

so i have this problem where: I have to accomplish a challenge A with n quests. Each quest gives me: p points and needs t time to be done. The object is to complete the challenge A that needs M ...
1answer
44 views

### How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables

I am reading a proof that the Subset Sum decision problem is NP-complete. I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. ...
1answer
42 views

2answers
75 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 ...
1answer
79 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 ...
0answers
45 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 ...
1answer
78 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 ...
1answer
54 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 ...
0answers
67 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 ...
1answer
122 views

0answers
96 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-...
1answer
746 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 ...
1answer
118 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 ...
2answers
151 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 ...
2answers
157 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 ...
0answers
112 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-...
1answer
70 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. ...
1answer
559 views

1answer
232 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 ...
1answer
73 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 ...
2answers
360 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\}$...