Fitting Shelves Problem: จัดชั้นวางให้เหลือพื้นที่น้อยที่สุดใน C++

ในปัญหานี้ เราได้รับความยาวผนัง W และขนาดชั้นวาง 2 ขนาด (n, m) งานคือหาวิธีวางชั้นวางให้พื้นที่เหลือน้อยที่สุด โดยให้ความสำคัญกับชั้นวางขนาดใหญ่ก่อน (คุ้มค่ากว่า)

ตัวอย่าง

Input: W = 12, n = 5, m = 3 Output: 0 4 0

วางชั้นขนาด 3 จำนวน 4 ชั้น = 12 ไม่เหลือพื้นที่

วิธีการแก้ปัญหา: Brute Force + Priority ให้ชั้นใหญ่

1. เริ่มจากวางชั้นขนาดเล็ก (m) ให้มากที่สุด
2. ลดจำนวนชั้นขนาดเล็กทีละ 1 แล้วเติมชั้นขนาดใหญ่ (n) แทน
3. เช็คพื้นที่เหลือ เก็บค่าที่เหลือน้อยที่สุด (ถ้าเท่ากัน ให้ชั้นใหญ่มากกว่า)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

void solveFittingShelves(int wall, int m, int n) {
    int numM = 0, numN = 0, minLeft = wall;
    int p = wall / m, q = 0, rem = wall % m;
    numM = p; numN = q; minLeft = rem;
    
    while (wall >= n) {
        q++; wall -= n;
        p = wall / m; rem = wall % m;
        if (rem <= minLeft) {
            numM = p; numN = q; minLeft = rem;
        }
    }
    cout << numM << " " << numN << " " << minLeft << endl;
}

int main() {
    int W = 29, m = 3, n = 9;
    cout << "Optimal Shelves fitting: ";
    solveFittingShelves(W, m, n);
    return 0;
}

ผลลัพธ์

Length of wall: 29, Shelves: 3 and 9
Optimal Shelves fitting: 0 3 2

วางชั้นขนาด 9 จำนวน 3 ชั้น = 27 เหลือพื้นที่ 2