贪心算法 部分背包问题给定一个最大容量为M的背包和N种食品,有食盐白糖大米等.已知第I种食品最多有WI公斤,价值为VI元每公斤,编程确定一个方案 使背包中食品总价最大
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/04 07:47:10
![贪心算法 部分背包问题给定一个最大容量为M的背包和N种食品,有食盐白糖大米等.已知第I种食品最多有WI公斤,价值为VI元每公斤,编程确定一个方案 使背包中食品总价最大](/uploads/image/z/8553866-50-6.jpg?t=%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95+%E9%83%A8%E5%88%86%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E6%9C%80%E5%A4%A7%E5%AE%B9%E9%87%8F%E4%B8%BAM%E7%9A%84%E8%83%8C%E5%8C%85%E5%92%8CN%E7%A7%8D%E9%A3%9F%E5%93%81%2C%E6%9C%89%E9%A3%9F%E7%9B%90%E7%99%BD%E7%B3%96%E5%A4%A7%E7%B1%B3%E7%AD%89.%E5%B7%B2%E7%9F%A5%E7%AC%ACI%E7%A7%8D%E9%A3%9F%E5%93%81%E6%9C%80%E5%A4%9A%E6%9C%89WI%E5%85%AC%E6%96%A4%2C%E4%BB%B7%E5%80%BC%E4%B8%BAVI%E5%85%83%E6%AF%8F%E5%85%AC%E6%96%A4%2C%E7%BC%96%E7%A8%8B%E7%A1%AE%E5%AE%9A%E4%B8%80%E4%B8%AA%E6%96%B9%E6%A1%88+%E4%BD%BF%E8%83%8C%E5%8C%85%E4%B8%AD%E9%A3%9F%E5%93%81%E6%80%BB%E4%BB%B7%E6%9C%80%E5%A4%A7)
贪心算法 部分背包问题给定一个最大容量为M的背包和N种食品,有食盐白糖大米等.已知第I种食品最多有WI公斤,价值为VI元每公斤,编程确定一个方案 使背包中食品总价最大
贪心算法 部分背包问题
给定一个最大容量为M的背包和N种食品,有食盐白糖大米等.已知第I种食品最多有WI公斤,价值为VI元每公斤,编程确定一个方案 使背包中食品总价最大
贪心算法 部分背包问题给定一个最大容量为M的背包和N种食品,有食盐白糖大米等.已知第I种食品最多有WI公斤,价值为VI元每公斤,编程确定一个方案 使背包中食品总价最大
对每件物品,以价值排序,每次优先选取价值大的,若物品选光则选次大的,直到背包装不下.
证明:
对第i件物品,若它是当前能选的物品中价值最大的,则选一公斤的该物品总比选一公斤的其他物品价值大.若你选取了一公斤价值为V1的物品,剩下了一公斤价值为V2的物品,而V2>V1,则只要将
两物品交换则能构造出一个更优的解,由此可知,上述的贪心是正确的.