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

#include #include #include using namespace std;

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

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

int main() { ifstream fin("input.txt"); // 从文件中读取输入 int n, W; fin >> n >> W; Item items[n]; for (int i = 0; i < n; i++) { fin >> items[i].weight >> items[i].value; // 读取每个物品的重量和价值 items[i].index = i + 1; // 记录物品序号 } fin.close();

sort(items, items + n, cmp); // 按单位价值从大到小排序

int current_weight = 0, current_value = 0;
int i = 0;
while (current_weight < W && i < n) { // 贪心选择物品
    if (current_weight + items[i].weight <= W) { // 如果当前物品能放入背包
        current_weight += items[i].weight; // 更新背包重量
        current_value += items[i].value; // 更新背包总价值
    }
    i++; // 继续遍历下一个物品
}

ofstream fout("output.txt"); // 输出到文件
fout << "Selected items: ";
for (int j = 0; j < i; j++) {
    fout << items[j].index << " "; // 输出选择的物品序号
}
fout << endl << "Total value: " << current_value << endl; // 输出背包总价值
fout.close();

return 0;

}

// 时间复杂度为O(nlogn)，主要是排序的时间复杂度。贪心算法本身只需要遍历一次物品，时间复杂度为O(n)。