Total number of combinations of $80$, $45$ and $27$ such that there sum is less than or equal to 180.

Question

I was going through the following optimization problem: Also there was a hint with this problem as:

Above are listed nine alternative ways to cut the paper. Clearly the wastage per roll is always less than $27$, because if we get $30$ cm as wastage then that means that we can still get a roll of $27$ cm and so the wastage is $3$. This one thing is clear to me. Is there any method by which I can get that total number of alternatives are nine OR I have to do it manually?

What I have done:

Out of $180$ cm roll we can get $0,1$ or $2$ rolls of $80$ cm, for $45$ cm roll we have options $0,1,2,3$ or $4$ and for $27$ cm roll we have options $0,1,2,3,4,5$ or $6$. From this information maximum number of combinations would be $3\times 5 \times 7=105$. Here I was unable to use the information that the wastage will be less than $27$ cm.

Next I listed all the possibilities as triplets:

$(0,0,0),(0,0,1),(0,0,2),....,(0,0,7)$

$(0,1,0),(0,1,1),(0,1,2),....,(0,1,7)$

$....................................$

$(0,4,0),(0,4,1),(0,4,2),....,(0,4,7)$

$(1,0,0),(1,0,1),(1,0,2),....,(1,0,7)$

$....................................$

$....................................$

$(2,4,0),(2,4,1),(2,4,2),....,(2,4,7)$

So now we have $15$ rows in total. And from each row at most we have only one entry which is suitable for us. Because if in a row we have $(a,b,c)$ as a suitable entry then that means that $(a,b,c-1)$ will give a wastage of more than $27$ cm so its not good for us and $(a,b,c+1)$ is not possible because $(a,b,c)$ has wastage less than $27$ cm. So we have $15$ rows so at most we have $15$ combinations which is suitable for us.

The last $5$ rows, rows with first entry as $2$. Out of all these we have only $(2,0,0)$ suitable for us. So out of last $5$ rows we have only one entry $(2,0,0)$ which is suitable for us. So now for the first $10$ rows we have at most $10$ suitable combinations and one from the last $5$ rows. Total will be maximum $10+1=11$.

Answer 1

The given nine patterns are all maximal patterns, and they are already listed in descending lexicographic order. We are given $m$ widths $w_1>w_2>\ldots>w_m$ and an upper bound $N$. An $m$-tuple $(x_1,\ldots, x_m)$ of numbers $x_i\in{\mathbb N}_{\geq0}$ is a maximal admissible pattern if $$\sum_{i=1}^m x_i\,w_i\leq N<\sum_{i=1}^m x_i\,w_i + w_m\ .$$ These patterns can be ordered lexicographically: $$x>y\qquad:\Leftrightarrow\qquad \exists r\geq1:\quad x_i=y_i\ (1\leq i\leq r-1)\quad\wedge \quad x_r>y_r\ .$$ The algorithm to obtain all such patterns in descending lexicographic order is difficult to verbalize. The idea is: Choose $x_1$ as large as possible and apply the algorithm to the widths $w_2> \ldots>w_m$ for the bound $N':=N-x_1 w_1$. When you are done, decrease $x_1$ by one, and repeat. Etcetera $\ldots$

At the beginning you obtain $x_1=2$ and $N'=180-2\cdot80=20$. Since $N'<w_3=27$ we have $x_i=0$ $(2\leq i\leq3)$. We therefore move to $x_1=1$ and have $N'=180-1\cdot 80=100$. The algorithm then says that we should choose $x_2=2$ and obtain $N''=100-2\cdot45=10$, which is already $<w_3$, so that $x_3=0$. We then move to $x_2=1$ and obtain $N''=100-1\cdot45=55$. This enforces $x_3=2$. We then move to $x_2=0$ and obtain $N''=N'=100$, so that necessarily $x_3=3$.

In this way we have constructed the patterns $(2,0,0)$, $(1,2,0)$, $(1,1,2)$, and $(1,0,3)$. Etcetera $\ldots$

Answer 2

Is there any method by which I can get that total number of alternatives are nine OR I have to do it manually?

Given $m>1$ widths $w_1>w_2>\ldots>w_m>0$ and an upper bound $N$ we can estimate the total number $A$ of alternatives as follows. Let an alternative has $x_i$ cutted rolls of width $w_i$ for each $i=1,\dots, m$. Remark that $\sum_{i=1}^{m-1}x_iw_i\le N$ and by the maximality of the alternative $x_m$ is defined uniquely, namely, $x_m=\left\lfloor\frac {N -\sum_{i=1}^{m-1}x_iw_i}{w_m}\right\rfloor$. Thus $A$ has a simple geometric interpretation as a quantity of all integer points contained in a simplex

$$S=\{(x_1,\dots, x_{m-1})\in\mathbb R^{m-1}: x_i\ge 0\mbox{ for each }i\mbox{ and } \sum_{i=1}^{m-1}x_iw_i\le N \}.$$

Thus $A$ approximately is equal to the volume $V(S)$ of $S$ (see here for the derivation of a formula for a volume of a simplex). More precisely,

$$\max\left\{\frac{(N-\sum_{i=1}^{m-1}w_i)^{m-1}}{(m-1)!\prod_{i=1}^{m-1}w_i},0\right\}=V(T^-)\le A\le V(T^+)=\frac{(N+\sum_{i=1}^{m-1}w_i)^{m-1}}{(m-1)!\prod_{i=1}^{m-1}w_i},$$ where $V(S^-)$ and $V(S^-)$ are volumes of the simplices

$$S^-=\{(x_1,\dots, x_{m-1})\in\mathbb R^{m-1}: x_i\ge 0\mbox{ for each }i\mbox{ and } \sum_{i=1}^{m-1}(x_i+1)w_i\le N \},$$

and

$$S^+=\{(x_1,\dots, x_{m-1})\in\mathbb R^{m-1}: x_i\ge 0\mbox{ for each }i\mbox{ and } \sum_{i=1}^{m-1}(x_i-1)w_i\le N \},$$

respectively.

In particular, for $w_1=80$, $w_2=45$, and $N=180$ the above formulae provide an approximation $A\simeq V(S)=4.5$ and bounds $1\le A\le 12 $.