โปรแกรม C++ ใช้ First Fit Decreasing สำหรับ 1-D Objects และ M Bins

บทนำ

นี่คือโปรแกรม C++ ใช้ First Fit Decreasing สำหรับ 1-D objects และ M bins

ฟังก์ชันและ Pseudocode ที่จำเป็น

Begin
  function binPack() คืนค่าจำนวน bins ที่ต้องการ:
    เริ่มต้น binC = 0
    เริ่มต้นอาร์เรย์เก็บ binVal
    วางไอเท็มทีละชิ้น
  function sort() ทำ bubble sort เรียงลำดับจากมากไปน้อย
End

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

#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(int argc, char **argv) {
    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;
}

ผลลัพธ์

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