有一个承重为W的背包和n个物品它们各自的重量和价值分别是wi和vi1=i=n。运用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)