证明背包问题具有贪心选择性质。
证明背包问题具有贪心选择性质。
发布时间：2025-07-23 18:42:43
请在 下方输入 要搜索的题目：
推荐参考答案 (
由 快搜搜题库 官方老师解答 )
答案：答:首先按物品的重量从小到大排序。贪心选择性质说的就是每次都是都是选取当前的最优值。假设背包问题每次都是从重量最小的物品开始选择的,那他一定满足贪心选择性质,假设背包问题不是从重量最小的物品开始选择的,那么说明重量最小的物品没有装入,现在我们用这个重量最小的物品代替当前选择装入的物品,依然可以得到一个最优解(装入的物品的个数相同)。所以背包问题具有贪心选择性质 for(i=0;istep); while(top->next){ pop(i,j); a[i][j]='*'; } for(i=0;i
