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

223 questions
Filter by
Sorted by
Tagged with
376 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 ...
94 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 ...
429 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\}$...
154 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 ...
67 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 ...
41 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-...
45 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: ...
1k 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 ...
77 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 ...
39 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 ...
34 views

48 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})$$...
772 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 ...
100 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$ ...
1k 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 ...
649 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 ...
473 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 ...
416 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 ...
1k 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\...