4 votes

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 ...
Discrete lizard's user avatar
  • 8,248
4 votes
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 ...
Steven's user avatar
  • 29.5k
3 votes
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 ...
A. G.'s user avatar
  • 261
3 votes

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)$ ...
Steven's user avatar
  • 29.5k
3 votes

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,...
D.W.'s user avatar
  • 159k
2 votes
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 ...
Mario Cervera's user avatar
2 votes
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$) ...
Yuval Filmus's user avatar
2 votes
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 ...
Yuval Filmus's user avatar
2 votes
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....
John L.'s user avatar
  • 39k
2 votes

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).
Yuval Filmus's user avatar
2 votes
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 ...
j_random_hacker's user avatar
2 votes
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 ...
Kaban-5's user avatar
  • 519
2 votes
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 ...
xskxzr's user avatar
  • 7,455
2 votes

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: ...
thunderbird30's user avatar
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 ...
D.W.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
orlp's user avatar
  • 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 ...
gnasher729's user avatar
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 ...
D.W.'s user avatar
  • 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$. ...
John L.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
e42d3's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
gnasher729's user avatar
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-...
Yuval Filmus's user avatar
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 ...
fade2black's user avatar
  • 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.
Bernd Strehl's user avatar
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 ...
Logan Leland's user avatar
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 ...
D.W.'s user avatar
  • 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 ...
gnasher729's user avatar

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