Untitled

#include <iostream>
#include <vector>

struct Item {
    std::string name;
    int Price;
    int Folower;
};

void knapsack(const std::vector<Item>& items, int capacity) {
    int n = items.size();

    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= capacity; ++w) {
            if (items[i - 1].Price <= w) {
                int includedFolower = items[i - 1].Folower + dp[i - 1][w - items[i - 1].Price];
                int excludedFolower = dp[i - 1][w];
                dp[i][w] = std::max(includedFolower, excludedFolower);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    std::vector<Item> selectedItems;
    int w = capacity;
    for (int i = n; i > 0 && w > 0; --i) {
        if (dp[i][w] != dp[i - 1][w]) {
            selectedItems.push_back(items[i - 1]);
            w -= items[i - 1].Price;
        }
    }

    std::cout << "Selected items:" << std::endl;
    for (const Item& item : selectedItems) {
        std::cout << "Name: " << item.name << ", Price: " << item.Price << ", Folower: " << item.Folower << std::endl;
    }
}

int main() {
    std::vector<Item> items = {
        {"Sơn Tùng", 2, 12},
        {"Trúc Nhân", 1, 10},
        {"Đen Vâu", 3, 40},
        {"Bích Phương", 2, 15}
    };

    int capacity = 5;

    knapsack(items, capacity);

    return 0;
}