Cで1枚の紙から切り取ることができる最大の与えられたサイズの長方形

1枚の紙の寸法、長さL、幅Bが与えられます。また、小さな長方形の寸法、長さl、幅bが与えられます。目標は、1枚の紙から切り取ることができる小さな長方形の最大数を見つけることです。

次の手順を実行します-

• まず、水平方向の配置、シートと長方形の長さLとlをそれぞれ取り上げます。 Lをlで、Bをbで整列し始め、長方形を数えます。

• 次に、垂直方向の配置でも同じことを行います。もう一度数えます。 countの最大値を返します。

例を挙げて理解しましょう。

入力

Sheet L=18, B=6 Rectangle l=4, b=3

出力

Maximum rectangles: 8

説明

Horizontal 18/4=4 6/3=2 2*4=8 rectangles possible
Vertical 18/3=6 6/4=1 6*1=6 rectangles possible
Maximum rectangles here is 8

入力

Sheet L=10, B=6 Rectangle l=4, b=2

出力

Maximum rectangles: 6

説明

Horizontal 10/4=2 6/2=3 2*3=6 rectangles possible
Vertical 10/2=5 6/4=1 5*1=5 rectangles possible
Maximum rectangles here is 6

以下のプログラムで使用されているアプローチは次のとおりです

• 変数LengthとBreadthは、シートの寸法を格納するために使用されます。

• 変数lenとbreは、長方形の寸法を格納するために使用されます。

• 関数maxRectangles（int L、int B、int l、int b）は、シートと長方形の寸法を取り、可能な長方形の最大数を返します。

• 変数numhとnumvは、水平方向と垂直方向にカットできる長方形の数を格納するために使用されます。

• 水平方向の場合、cols =L/lとrows=B / bを分割し、長方形を使用できます。numh=cols*rows。

• 垂直方向の場合、cols =L/bとrows=B / lを分割し、長方形を使用できます。numv=cols*rows。

• 上記の2つのステップnumhまたはnumvで得られた結果として最大値を返します。

例

#include <stdio.h>
int maxRectangles (int L, int B, int l, int b){
   int numh = 0, numv = 0;
   // Cut rectangles horizontally if possible
   if (l <= L && b <= B){
      // One rectangle is a single cell
      int cols = B / b;
      int rows = L / l;
      // Total rectangles = total cells
      numh = rows * cols;
   }
   // Cut rectangles vertically if possible
   if (l <= B && b <= L){
      int cols = L / b;
      int rows = B / l;
      numv = rows * cols;
   }
   // Return the maximum possible rectangles
   return numh>numv?numh:numv;
}
// Driver code
int main (){
   int Length = 18;
   int Breadth =6;
   int len = 4, bre = 3;
   printf("Maximum rectangles: %d",maxRectangles(Length,Breadth,len,bre));
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Maximum given sized rectangles that can be cut out of a sheet of paper: 8