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

246 questions
Filter by
Sorted by
Tagged with
433 views

### How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
1 vote
446 views

### How to make the standard DP algorithm for 0/1 Knapsack make larger steps?

The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution. Is there any approach to the knapsack problem that does not require ...
1k views

### Find 8 numbers whose sum is closest to a defined value

I have a file that has a number (a positive integer) on each row. Given a number $q$, I want to find a value that's a sum of some 8 numbers in the file, and is as close to $q$ as possible. So, ...
44 views

### Algorithms for keeping number of backups constant

The problem is quite simple: backups are done at regular time intervals (with possible but rare exceptions). The storage however is not unlimited, and only a certain number of backups can be stored, ...
1k views

605 views

### Dynamic programming for counting knapsack solutions

Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I ...
180 views

### Heuristics and libraries for the knapsack problem

A student of mine is studying the knapsack problem (0-1 with a single objective). She is also talking to an industry partner who has realistic problems she can try solving (between 1000 to 10000 items)...
50 views

### Spandex knapsack?

I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple ...
217 views

### Complexity of a knapsack variant

Consider the following traditional integer knapsack problem: $\max \sum_{i=1}^k p_i \cdot x_i\\ \text{s.t.} \sum_{i=1}^k w_i \cdot x_i \leq W \\ x_i \in \{0,\ldots,k_i\} \text{ for each } i$ Now ...
142 views

### Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem

I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is ...
471 views

### Output of well-known algorithms for the Subset sum problem

According to Wikipedia: In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set (or multiset) of integers, is ...
135 views

I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same: Maximize the value of ($\sum_{i=1}^n v_i \cdot x_i) + B \cdot \frac{... 2 votes 1 answer 1k views ### Subset sum algorithm in O(n³ log n)? I think that I have found an algorithm which resolve exactly the subset sum problem in$O(N^3)$in the worst case, only for positive numbers. After my research, I'm lost between all the algorithms ... 8 votes 1 answer 6k views ### Balanced Weight Distribution in Bins/Buckets Let$W = \{w_1,w_2,...w_n\}$be a set of integer weights. Let$B = \{b_1,b_2,...b_m\}$be a set of buckets, with$m \leq n$. Let$T(b_j)$represent the total weight present in bucket$b_j$, which is ... 2 votes 3 answers 17k views ### Brute force method to solve the 0-1 knapsack problem I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following: If the brute force ... -1 votes 1 answer 366 views ### Solving a Variation of knapsack [closed] I'm working on a problem which to me, seems very similar to a knapsack problem: A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store ... 4 votes 2 answers 1k views ### What's the big deal with the knapsack problem? In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -> 234-tree -> red-black tree -> heap -> greedy algorithms -> dynamic ... -1 votes 1 answer 479 views ### Unlimited Knapsack Problem How would I solve the unbounded knapsack problem, only this time aiming to maximize the weight instead of the value? 5 votes 4 answers 4k views ### Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? On the wikipedia page for the knapsack problem it says that the runtime is$\mathcal{O} (nW)$and goes on to say that this doesn't violate its classification as NP because the input size is related to ... 2 votes 1 answer 565 views ### Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)? According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ... 5 votes 0 answers 159 views ### Rate Pooling Optimization Algorythim I have thousands of wireless LTE hotspots. Each month I need to assign each hotspot a rate plan. Each hotspot uses some amount of data in a month (represented in megabytes). Each rate plan has some ... 3 votes 1 answer 5k views ### Dynamic Programming Solution to 0,1 KnapSack Problem I am trying to understand the DP solution to the basic knapsack problem.However even after reading through a variety of tutorials ,its still beyond my comprehension.I am taking an algorithmics course ... 9 votes 1 answer 464 views ### What algorithms exist for solving natural number linear systems? I'm looking at the following problem: Given$n$-dimensional vectors of natural numbers$v_1, \ldots, v_m$and some input vector$u$, is$u$a linear combination of the$v_i$'s with natural number ... 1 vote 3 answers 7k views ### Correctness proof of greedy algorithm for 0-1 knapsack problem We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an ... 1 vote 0 answers 437 views ### Integer knapsack problem with bounded weights Is there any literature about the complexity of the integer knapsack problem with bounded weights? To make it clear, I want an optimal solution to the following problem:$\max \sum_{i=1}^k c_i \cdot ...
67 views

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
15k views

10k views

### Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum. Now I'm not sure if a greedy algorithm will do the trick. That is, sort by ...
272 views

### Maximizing profit

Problem: Given 11 numbers {N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11} where N1:amount of profit from product A N2:amount of profit from Product B N3:amount of time ...
1k views

### Dynamic Knapsack Problem - Algorithms and References

I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
2k views

### Knapsack problem with multiple constraints

I am unsure if I have even identified the problem correctly, but reading up on knapsack problem seems the closest to what I am trying to solve: A cook has $k$ ingredients of $p$ quantities. Given a ...
1k views

### Algorithm to pack any small boxes into a big box

I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains ...
2k views

### Relations between the knapsack problem, the bin packing problem, and the set packing problem?

I wonder what relations are between the knapsack problem, the bin packing problem and the set packing problem? From their mathematical formulations, I don't see the first two belong to the third one ...
1k views

### Adjacent house , dynamic programming problem

I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be ...
316 views

1 vote