有一个承重为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 ((double)a.value / a.weight) > ((double)b.value / b.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 }); } fin.close(); sort(items.begin(), items.end(), cmp); // 排序 int cur_weight = 0; // 当前背包重量 int cur_value = 0; // 当前背包价值 vector ans; // 存储放入背包的物品编号 for (int i = 0; i < n; i++) { if (cur_weight + items[i].weight <= w) { // 如果可以放入背包 cur_weight += items[i].weight; cur_value += items[i].value; ans.push_back(items[i].index); } } cout << "物品序号列表："; for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } cout << endl; cout << "总价值：" << cur_value << endl; return 0; }

// 时间复杂度：O(nlogn) // 排序的时间复杂度为O(nlogn)，放入背包的时间复杂度为O(n)，所以总时间复杂度为O(nlogn + n) = O(nlogn) // 递推：从第1个物品到第n个物品，依次考虑是否放入背包，最终得到最优解