Question

请教我用python的贪心法做0/1背包问题

要求根据重量最轻、价值最大、单位重量的价值最大三种贪心原则来选取装物品方式
拜托写出代码还稍微解释一下，我不是要应付作业是真的想学明白这个东西！谢谢
ps：物品的重量和价值，要是不按照大小顺序排列，要怎么做？

Answer 1

动态规划，可以给你说下思路。
我们用一个二维的矩阵A来存储中间结果，A[i][j]代表前i个物体装入容量为j的背包时可以得到的最优解，相当于是原问题的一个子问题，然后我们就可以写出递推式来更新这个矩阵，具体可以参考下详细的讲解，网上的博客非常多不用我再写一遍。

比如这种：http://zh.wikipedia.org/zh-cn/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98
先自己读一遍吧，有问题可以再问。

追问

要求根据重量最轻、价值最大、单位重量的价值最大三种方式输出价值，这要怎么办呢?

Answer 2

贪心算法用于普通背包，01背包的普遍解法为动态规划

追问

贪心法完全做不了吗？
那就请教我用动态规划吧。。。谢谢