Bài toán ghép kệ (Fitting Shelves Problem) trong C++

Cho chiều dài tường W, hai loại kệ kích thước n và m. Nhiệm vụ: ghép kệ sao cho không gian thừa nhỏ nhất, ưu tiên kệ lớn hơn (hiệu quả chi phí hơn).

Ví dụ minh họa

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

Ghép 4 kệ size 3, tổng chiều dài 12, không thừa chỗ.

Phương pháp giải

Thử tất cả tổ hợp số lượng kệ lớn (n) từ 0 đến max, tính số kệ nhỏ (m) phù hợp, chọn tổ hợp có không gian thừa nhỏ nhất. Ưu tiên kệ lớn hơn.

Ví dụ chương trình

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

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

int main(){
    int W = 29, m = 3, n = 9;
    cout << "Chiều dài tường: " << W << endl;
    cout << "Kích thước kệ: " << m << "\t" << n << endl;
    cout << "Ghép kệ tối ưu: ";
    solveFittingShelves(W, m, n);
    return 0;
}

Kết quả

Chiều dài tường: 29
Kích thước kệ: 3	9
Ghép kệ tối ưu: 0 3 2