โปรแกรม C++ แก้ปัญหา Fractional Knapsack

ในปัญหา Fractional Knapsack มีชุดของรายการ แต่ละรายการมีน้ำหนักและค่า เราต้องแบ่งรายการเพื่อเพิ่มค่ารวมของกระเป๋า และสามารถทำได้ด้วย greedy approach

อัลกอริทึม

Begin
    สร้างอาร์เรย์ของโครงสร้าง Item
    ประกาศ value, weight, knapsack weight และ density
    คำนวณ density = value/weight สำหรับแต่ละรายการ
    เรียงลำดับอาร์เรย์ items ตามลำดับ density ลดลง
    เราเพิ่มค่าจากด้านบนของอาร์เรย์ไปยัง total value จนกระเป๋าเต็ม คือ total value <= W
End

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

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

typedef struct {
    int v;
    int w;
    float d;
} Item;

void input(Item items[], int sizeOfItems) {
    cout << "Enter total " << sizeOfItems << " item's values and weight" << endl;
    for(int i = 0; i < sizeOfItems; i++) {
        cout << "Enter " << i+1 << " V ";
        cin >> items[i].v;
        cout << "Enter " << i+1 << " W ";
        cin >> items[i].w;
    }
}

void display(Item items[], int sizeOfItems) {
    int i;
    cout << "values: ";
    for(i = 0; i < sizeOfItems; i++) {
        cout << items[i].v << "\t";
    }
    cout << endl << "weight: ";
    for (i = 0; i < sizeOfItems; i++) {
        cout << items[i].w << "\t";
    }
    cout << endl;
}

bool compare(Item i1, Item i2) {
    return (i1.d > i2.d);
}

float knapsack(Item items[], int sizeOfItems, int W) {
    int i, j;
    float totalValue = 0, totalWeight = 0;
    
    for (i = 0; i < sizeOfItems; i++) {
        items[i].d = (float)items[i].v / items[i].w; // typecasting (v เป็น int และ w เป็น int ผลลัพธ์ d จะเป็น int)
    }
    
    sort(items, items+sizeOfItems, compare);
    
    for(i=0; i<sizeOfItems; i++) {
        if(totalWeight + items[i].w <= W) {
            totalValue += items[i].v;
            totalWeight += items[i].w;
        } else {
            int wt = W - totalWeight;
            totalValue += (wt * items[i].d);
            totalWeight += wt;
            break;
        }
    }
    
    cout << "Total weight in bag " << totalWeight << endl;
    return totalValue;
}

int main() {
    int W;
    Item items[4];
    input(items, 4);
    cout << "Entered data \n";
    display(items,4);
    cout<< "Enter Knapsack weight \n";
    cin >> W;
    float mxVal = knapsack(items, 4, W);
    cout << "Max value for " << W << " weight is " << mxVal;
}

ผลลัพธ์

Enter total 4 item's values and weight
Enter 1 V
Enter 1 W
Enter 2 V
Enter 2 W
Enter 3 V
Enter 3 W
Enter 4 V
Enter 4 W
Entered data
values: 2      0      0      0
weight: 0      490642064 0      4196544
Enter Knapsack weight
Total weight in bag 0
Max value for 0 weight is 2