1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – darij grinberg Sep 26 '18 at 17:59
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – darij grinberg Sep 29 '18 at 2:37
  • $\begingroup$ 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. $\endgroup$ – antkam Sep 29 '18 at 4:02
  • $\begingroup$ I'm not convinced yet. You seem to be considering only a specific class of SUBSET SUM problems. $\endgroup$ – darij grinberg Sep 29 '18 at 4:35
  • $\begingroup$ 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. $\endgroup$ – antkam Sep 29 '18 at 5:31
  • $\begingroup$ Oh, you're looking at the equivalent problem! Then I agree. $\endgroup$ – darij grinberg Sep 29 '18 at 6:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.