有一个承重为W的背包和n个物品它们各自的重量和价值分别是wi和vi1=i=n。运用C++写一段代码并在每行代码后面注释。用文件输入的方法应用贪心算法求解离散背包问题。cout显示放到背包中的物品的序号列表和总价值。并分析时间复杂度

#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});
}

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);
    }
}

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为物品的个数，主要是排序的时间复杂度