Chương trình C++ cài đặt First Fit Decreasing cho đối tượng 1-D và M bin

Cài đặt thuật toán First Fit Decreasing (FFD) cho bài toán đóng gói bin 1 chiều.

Hàm và mã giả

Bắt đầu
  hàm binPack() trả về số bin cần.
    Khởi tạo binC = 0, mảng binVal.
    Đặt vật品 lần lượt.
  hàm sort() sắp xếp giảm dần (bubble sort).
Kết thúc

Ví dụ

#include <iostream>
using namespace std;

void binPack(int *a, int s, int n) {
    int binC = 0;
    int binVal[n];
    for (int i = 0; i < n; i++) binVal[i] = s;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (binVal[j] - a[i] >= 0) {
                binVal[j] -= a[i];
                break;
            }
    for (int i = 0; i < n; i++)
        if (binVal[i] != s) binC++;
    cout << "Number of bins required using first fit decreasing algorithm is: " << binC;
}

int* sort(int *seq, int n) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n - 1; j++)
            if (seq[j] < seq[j + 1]) {
                seq[j] = seq[j] + seq[j + 1];
                seq[j + 1] = seq[j] - seq[j + 1];
                seq[j] = seq[j] - seq[j + 1];
            }
    return seq;
}

int main() {
    cout << "Enter the number of items in Set: ";
    int n; cin >> n;
    cout << "Enter " << n << " items:";
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << "Enter the bin size: ";
    int s; cin >> s;
    int *seq = sort(a, n);
    binPack(seq, s, n);
    return 0;
}

Kết quả

Enter the number of items in Set: 7
Enter 7 items: 4 6 7 5 3 2 1
Enter the bin size: 5
Number of bins required using first fit decreasing algorithm is: 3