Manufacturing desired planks from an existing pile of planks

Question

Suppose there is a pile of commensurable planks that only may differ in lengths $0<a_1\leq\cdots\leq a_m$, which are to be used to manufacture planks of length: $0<b_1\leq\cdots\leq b_n$.

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<b_1$ 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?

Answer 1

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... :)