# Manufacturing desired planks from an existing pile of planks

Suppose there is a pile of commensurable planks that only may differ in lengths $$0, which are to be used to manufacture planks of length: $$0.

Algorithm:
$$A$$ is the list of existent planks
$$B$$ is the list of wanted planks

1. If $$B$$ is empty return 'success'
2. If $$a_m return 'failure'
3. Remove the smallest plank $$a_i\geq b_1$$ from list $$A$$
4. Manufacture the greatest plank $$b_j\leq a_i$$ by, if necessary, cut $$a_i$$ into planks of length $$b_j$$ and $$a^\prime_i$$
5. Return what's left ($$a^\prime_i$$) to $$A$$
6. Remove $$b_j$$ from the list $$B$$
7. Goto 1.

I conjecture that this algorithm is optimal in two ways:

1. If the manufacturing is possible in any way, it is also possible by the algorithm.
2. The square sum of the lengths of the remaining planks in $$A$$ is maximal compared to other cuttings.

Is this possible to prove or disprove?

• Note for googling purposes: The problem your algorithm tries to solve is checking whether the integer partition $\left(b_n, \ldots, b_1\right)$ is a refinement of the partition $\left(a_m, \ldots, a_1\right)$ (and if so, finding a witness). I'd suspect Knuth's TAoCP has something to say about this. – darij grinberg Sep 26 '18 at 17:59

If I understand you correctly, this is a counterexample:

$$A = \{10, 12\}$$ and $$B = \{4, 5, 6, 7\}$$. There is a unique solution: $$10=4+6, 12=5+7$$. However your algorithm would do this in its first iteration:

• (step 3): remove plank $$10$$

• (step 4): manufacture $$7$$ from $$10$$ leaving $$3$$

• (steps 5 & 6): now $$A=\{3,12\}$$ and $$B=\{4,5,6\}$$ and it's impossible to complete the job.

More importantly, the problem you pose is a generalization of SUBSET SUM: https://en.wikipedia.org/wiki/Subset_sum_problem which asks: Given a set of integers $$B$$, is there a subset that sums to $$a_1$$? The SUBSET SUM problem is NP-complete, and is a special case of your problem, and your algorithm is polynomial, which makes it unlikely to work... :)

• Are you sure the problem is a generalization of SUBSET SUM? What if the B-planks cannot be made from the A-planks, but SUBSET SUM nevertheless has positive answers which lead to dead-ends? (I agree with your counterexample, though.) – darij grinberg Sep 29 '18 at 2:37
• it is a generalization in the sense that, any SUBSET SUM problem can be mapped into a plank problem, s.t. if you can solve the plank problem you can also solve the subset sum. the mapping is simply: a subset sum problem with inputs $B$ and $a_1$ gets mapped to a plank problem with the same $B$ and $A = \{a_1, sum(B) - a_1\}$. then the subset sum has a solution iff the plank problem has a solution. i am not 100% sure "generalization" is the right technical term for this kind of mapping, but this is what i mean. – antkam Sep 29 '18 at 4:02
• I'm not convinced yet. You seem to be considering only a specific class of SUBSET SUM problems. – darij grinberg Sep 29 '18 at 4:35
• according to wikipedia: SUBSET SUM is "given a set of integers [what I call $B$] and an integer s [my $a_1$], does any non-empty subset sum to s?" I then simply calculate $a_2 = ( \sum_{b \in B} b ) - a_1$ and construct $A=\{a_1, a_2\}$ and consider it a PLANK problem. If a PLANK algorithm can find a solution, then the $a_1$ part of the PLANK solution solves the original SUBSET SUM problem. – antkam Sep 29 '18 at 5:31
• Oh, you're looking at the equivalent problem! Then I agree. – darij grinberg Sep 29 '18 at 6:19