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

2024-12-04 03:40:02

推荐回答（2个）

回答（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
先自己读一遍吧，有问题可以再问。

回答（2）：

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