Chương trình C++ giải bài toán cái ba lô phân số (Fractional Knapsack)

Trong bài toán cái ba lô phân số (Fractional knapsack), một tập hợp vật phẩm được cho, mỗi vật phẩm có một trọng lượng và một giá trị. Chúng ta cần chia nhỏ vật phẩm để tối đa hóa tổng giá trị của ba lô và điều này có thể thực hiện theo phương pháp tham lam (greedy).

Thuật toán

Bắt đầu
    Lấy mảng cấu trúc Item
    Khai báo giá trị, trọng lượng, trọng lượng ba lô và mật độ
    Tính mật độ = giá trị/trọng lượng cho mỗi vật phẩm
    Sắp xếp mảng vật phẩm theo thứ tự mật độ giảm dần
    Thêm giá trị từ đầu mảng vào tổng giá trị cho đến khi ba lô đầy, tức là tổng trọng lượng <= W
Kết thúc

Mã ví dụ

#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 << "Nhập tổng " << sizeOfItems << " giá trị và trọng lượng của vật phẩm" << endl; 
    for(int i = 0; i < sizeOfItems; i++) { 
        cout << "Nhập " << i+1 << " V "; 
        cin >> items[i].v; 
        cout << "Nhập " << i+1 << " W "; 
        cin >> items[i].w; 
    } 
} 

void display(Item items[], int sizeOfItems) { 
    int i; 
    cout << "Giá trị: "; 
    for(i = 0; i < sizeOfItems; i++) { 
        cout << items[i].v << "\t"; 
    } 
    cout << endl << "Trọng lượng: "; 
    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; //ép kiểu (v là int và w cũng là int nên giá trị cuối của d sẽ là int) 
    } 
    sort(items, items + sizeOfItems, compare); 
    /* 
    bỏ comment nếu cần kiểm tra dữ liệu sau khi sắp xếp 
    cout << "Giá trị: "; 
    for(i = 0; i < sizeOfItems; i++) { 
        cout << items[i].v << "\t"; 
    } 
    cout << endl << "Trọng lượng: "; 
    for (i = 0; i < sizeOfItems; i++) { 
        cout << items[i].w << "\t"; 
    } 
    cout << endl << "Tỷ lệ: "; 
    for (i = 0; i < sizeOfItems; i++) { 
        cout << items[i].d << "\t"; 
    } 
    cout << endl; 
    */ 
    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 << "Tổng trọng lượng trong ba lô: " << totalWeight << endl; 
    return totalValue; 
} 

int main() { 
    int W; 
    Item items[4]; 
    input(items, 4); 
    cout << "Dữ liệu đã nhập \n"; 
    display(items, 4); 
    cout << "Nhập trọng lượng ba lô \n"; 
    cin >> W; 
    float mxVal = knapsack(items, 4, W); 
    cout << "Giá trị tối đa cho " << W << " trọng lượng là " << mxVal; 
}

Kết quả

Nhập tổng 4 giá trị và trọng lượng của vật phẩm 
Nhập 1 V 
Nhập 1 W 
Nhập 2 V 
Nhập 2 W 
Nhập 3 V 
Nhập 3 W 
Nhập 4 V 
Nhập 4 W 
Dữ liệu đã nhập 
Giá trị: 2 0 0 0 
Trọng lượng: 0 490642064 0 4196544 
Nhập trọng lượng ba lô 
Tổng trọng lượng trong ba lô 0 
Giá trị tối đa cho 0 trọng lượng là 2