C++ 贪心算法求解离散背包问题

#include #include #include #include

using namespace std;

struct Item { int weight; int value; int index; };

bool cmp(Item a, Item b) { return a.value * b.weight > b.value * a.weight; // 按照单位价值排序 }

int main() { int W, n; vector items;

ifstream fin("input.txt"); // 从文件读取输入数据
fin >> W >> n;

for (int i = 1; i <= n; i++) {
    int weight, value;
    fin >> weight >> value;
    items.push_back({weight, value, i}); // 将物品信息存入 items 向量
}

sort(items.begin(), items.end(), cmp); // 按照单位价值排序

int totalValue = 0;
vector<int> selectedItems;

for (int i = 0; i < n; i++) {
    if (W >= items[i].weight) { // 如果当前物品可以放进背包
        W -= items[i].weight; // 更新剩余容量
        totalValue += items[i].value; // 更新总价值
        selectedItems.push_back(items[i].index); // 将物品序号加入 selectedItems 向量
    }
}

cout << "Selected items: ";
for (int i = 0; i < selectedItems.size(); i++) {
    cout << selectedItems[i] << " ";
}
cout << endl;
cout << "Total value: " << totalValue << endl;

fin.close();

return 0;

}

// 时间复杂度为O(nlogn)，其中n为物品的个数，主要是排序的时间复杂度。