# Tag Info

### Fitting different rectangles inside a rectangle

As mentioned in the comments, this problem is known to be NP-hard. So, the only fast algorithms you're going to get will be approximation algorithms or heuristic. As this is a common practical problem ...
• 8,248
Accepted

### Bin packing when items can be broken

Here is a proof that the problem remains hard when $k=1$. For simplicity it uses an item of size equal to the bin capacity. If you require each item to be smaller than the bin capacity you can ...
• 29.5k
Accepted

### Algorithm for packing various shapes inside of a rectangle

As pointed out by the other answer, this is an example of bin packing, a type of problem that is NP-complete. Skiena Section 17.9 reports: Fortunately, relatively simple heuristics tend to work ...
• 261

### One-dimensional packing problem: Optimal decomposition of music structure

If $n'$ is the number of groups, this problem admits no $2^{o(n')}$-time algorithm for any choice of a constant $\epsilon > 0$, unless the exponential time hypothesis (ETH) fails. Let $G = (V, E)$ ...
• 29.5k

### Nesting algorithm for rectangular-based, fixed-orientation polygons

I will describe how you can solve this with an ILP (integer linear programming) solver. For the size of problem you have, I expect it will work acceptably well. Let's focus on just two of your shapes,...
• 159k
Accepted

### Does a greedy strategy exist for this instance of the Bin Packing Problem?

No, a greedy approach would not guarantee a solution for this problem (regardless of whether this solution is optimal or not). To see why, proceed by reduction. Suppose that you could actually find a ...
• 3,704
Accepted

### Dividing bins into segments

For $0 \leq i \leq pm+1$, define $$x_i = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor.$$ We put ball $i$ in bin $i$ for $1 \leq i \leq pm$. The length of the $i$th space (for $1 \leq i \leq pm+1$) ...
• 277k
Accepted

### Constructing an optimal solution to bin packing using a "magical function" $\phi$

Starting with $W$, repeatedly try to find two weights $w_i,w_j$ such that merging them (i.e., replacing both of them with $w_i+w_j$) doesn't increase the number of bins needed. Eventually, you will be ...
• 277k
Accepted

### How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?

P is in big-endian format. P0 —0111011011010011001011010010011001011001010010001011011010000001, The first bit, 0, means 2*0 + 1 = 1 is not a prime. The second bit, 1, means 2*1 + 1 = 3 is a prime....
• 39k

### Reducing 3 SAT to 3 SET PACKING

Your problem is known as 3-dimensional matching, or 3DM. It is one of the 21 problems proved to be NP-hard in Karp's original paper (number 17 on his list).
• 277k
Accepted

### Optimize stacking time series by offsetting start times (feels like a backpack problem?)

I suspect this problem is NP-hard, but haven't been able to prove it. In any case, Integer Linear Programming (ILP) is a good way to solve it. Let $c_1, \dots, c_n$ be the series data. For each valid ...
• 5,479
Accepted

### Can this special case of bin packing be solved in polynomial time?

Yes, there is a polynomial time solution. It is not very pretty, so simplifications or alternative approaches are welcome. TL;DR: the exact weights are rarely important, so we can round them up to a ...
• 519
Accepted

### What is the approximation ratio of this bin-backing algorithm?

We show that $\mathrm{ALG} \le (3/2) \mathrm{OPT} + 1$, and in some cases $\mathrm{ALG} \ge (3/2) \mathrm{OPT} -1/2$ even when the number of items is big enough. There is still a gap between the two ...
• 7,455

### Is the flexible bin packing problem NP-complete?

Here is a potential solution that I came up with for the above problem. Could someone please verify my explanation for why F-BPP is in NP and my reduction of BPP to F-BPP? Proof: F-BPP is in NP: ...
1 vote
Accepted

### Bin packing variant for maximizing value in a bin

This is the knapsack problem. It is NP-complete, so there are no algorithms that are both efficient on all problem instances and always optimal, but there are many different techniques that yield ...
• 159k
1 vote
Accepted

### Optimal way to pack items with multidimensional weight such that the number of items is minimized?

This problem is NP-hard, so you can't expect a general algorithm that is efficient and always correct. In particular, in the special case where the goal vector has only 1's and 0's in it, it becomes ...
• 159k
1 vote
Accepted

### Why we can't have some algorithm to be polynomial if there are generic conditions that make them so?

It's often the case that an NP-complete problem has some parameter $b$ that when fixed to a small constant makes an polynomial algorithm possible, yes. However in fixing $b$ that problem (at least as ...
• 13.4k
1 vote

### Approximate bin-packing?

I assume you want to put items $w_1$ to $w_{i_1}$ into the first bin, $w_{i_1+1}$ to $w_{i_2}$ into the second bin, etc. etc. The number n of bins is given. This can be done with something similar to ...
• 30k
1 vote
Accepted

### packing with time-variant weights

I'd suggest formulating this as an instance of SAT or ILP, then using an off-the-shelf SAT or ILP solver. This smells like the kind of problem that might be NP-hard in general and thus it might not ...
• 159k
1 vote
Accepted

### Greedy algorithm Packing problem

I would not believe there is a greedy algorithm that can do the job. Instead, sorting followed by dynamic programming as indicated by j_random_hacker's comment seems the appropriate way to find $L$. ...
• 39k
1 vote
Accepted

### Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k

This problem is NP-complete. Even testing whether there exists a single subset that sums to $k$ is NP-complete; that is known as the subset sum problem. Therefore, you should not expect any ...
• 159k
1 vote
Accepted

### Genetic algorithm - fit max circles inside box - what chromossomes?

You can define chromosome as array - coordinates of the center of a circle - [(x1,y1), (x2, y2),..,(xn,yn)] One required condition for every circle- no intersection between sides of rectangle and ...
• 36
1 vote
Accepted

### Genetic Algorithm - Fit max circles inside box

In genetic algorithms, each individual should be a candidate solution to the problem. You're trying to find a packing of circles into the box, so each individual should be a complete packing that ...
• 159k
1 vote

### Bin-packing satisfiability rather than minimization

Having a fixed number of bins makes little difference. If you use sorted-first-fit for example, the only difference is that the algorithm can fail. On the other hand, if you use a better algorithm for ...
• 30k
1 vote
Accepted

### Bin packing with item weight constraint

Assuming that you mean the usual bin packing problem, your question is answered on Wikipedia, on the page on strong NP-completeness. A problem is strongly NP-complete exactly when it remains NP-...
• 277k
1 vote
Accepted

### How to classify a 3D "Knapsack" problem where the only limitation is space, i.e. there is no weight constraint?

In the standard Knapsack problem (solvable by DP) when we are packing objects we do not care about how we put objects in the knapsack, i.e., what only matters is a subset of objects and the sum of ...
• 9,837
1 vote

### Group values up to a threshold and minimize groups

I just learned that this is the bin packing problem with goal of minimizing the bins. This problem is NP hard. So the greedy strategy wont guarantee an optimal solution.
• 133
1 vote

### Is packing a bag of presents easier for Rupert than Santa?

After quickly looking at this question, I believe Rupert's extra knowledge of each child's {behavior, max value present} will not always make Santa's job easier. Santa will still need to perform a 0/1 ...
• 160
1 vote

### Help me identify the type of Knapack Problem I am dealing with

There's no special "name" for this problem that I'm aware of. Don't assume that problem specifications this specific will necessarily have a "name" or "type". Instead, it's simply one of many ...
• 159k
1 vote

### Packing chocolate boxes

The greedy algorithm will find an optimal solution: As long as there are more than k different chocolates, fill a box with one each of the k chocolates where the most pieces are left. Then as long as ...
• 30k

Only top scored, non community-wiki answers of a minimum length are eligible