หาจำนวนสี่เหลี่ยมเล็กที่ตัดได้จากกระดาษแผ่นใหญ่ใน C

แนวคิด

ลองวาง 2 ทิศทาง แล้วเลือกค่าสูงสุด:

1. Horizontal: ความยาวกระดาษ // ความยาวสี่เหลี่ยม, ความกว้างกระดาษ // ความกว้างสี่เหลี่ยม
2. Vertical (หมุน 90°): ความยาวกระดาษ // ความกว้างสี่เหลี่ยม, ความกว้างกระดาษ // ความยาวสี่เหลี่ยม

สูตร

// Horizontal
cols_h = L / l;
rows_h = B / b;
count_h = cols_h * rows_h;

// Vertical (Rotated)
cols_v = L / b;
rows_v = B / l;
count_v = cols_v * rows_v;

Answer = max(count_h, count_v);

ตัวอย่างที่ 1

Sheet: L=18, B=6
Rect:  l=4, b=3

Horizontal: 18/4=4, 6/3=2 → 4×2=8
Vertical:   18/3=6, 6/4=1 → 6×1=6
Max = 8

ตัวอย่างที่ 2

Sheet: L=10, B=6
Rect:  l=4, b=2

Horizontal: 10/4=2, 6/2=3 → 2×3=6
Vertical:   10/2=5, 6/4=1 → 5×1=5
Max = 6

โปรแกรม C สมบูรณ์

#include 

int maxRectangles(int L, int B, int l, int b) {
    int count_h = 0, count_v = 0;
    
    // Horizontal orientation
    if (l <= L && b <= B) {
        int cols = L / l;
        int rows = B / b;
        count_h = cols * rows;
    }
    
    // Vertical orientation (rotated 90°)
    if (b <= L && l <= B) {
        int cols = L / b;
        int rows = B / l;
        count_v = cols * rows;
    }
    
    return (count_h > count_v) ? count_h : count_v;
}

int main() {
    int L, B, l, b;
    
    printf("Sheet Length: "); scanf("%d", &L);
    printf("Sheet Breadth: "); scanf("%d", &B);
    printf("Rect Length: "); scanf("%d", &l);
    printf("Rect Breadth: "); scanf("%d", &b);
    
    int result = maxRectangles(L, B, l, b);
    printf("Maximum rectangles: %d\n", result);
    
    return 0;
}

ผลลัพธ์ตัวอย่าง:

Sheet Length: 18
Sheet Breadth: 6
Rect Length: 4
Rect Breadth: 3
Maximum rectangles: 8

ข้อสมมติและข้อจำกัด

• ตัดเฉพาะแบบ **Axis-Aligned** (ไม่หมุนมุมอื่น)
• ไม่พิจารณา **Guillotine Cutting Constraint** (ตัดต้องเป็นเส้นตรงจากขอบถึงขอบ)
• ไม่พิจารณา **Waste Minimization** (เพียงแค่ Max Count)
• Integer Division (ปัดทิ้งเศษ) - เหมาะกับการตัดจริง

ขยายความ: 2D Bin Packing Problem

ปัญหานี้เป็นกรณีง่ายของ **2D Bin Packing / Cutting Stock Problem** ซึ่งเป็น NP-Hard สำหรับรูปทรงไม่สม่ำเสมอ หรืออนุญาตหมุนอิสระ