Question

如何理解背包问题

Answer 1

解决方法：
最佳的解决方法是使用动态规划——先得到该问题的局部解然后扩展到全局问题解。
构建物品X在不同重量时的价值数组V(Value数组)：
V[N][W] = 4 rows * 10 column
该矩阵中的每个值的求解都代表一个更小的背包问题。
初始情况一：对于第0列，它的含义是背包的容量为0。此时物品的价值呢？没有。因此，第一列都填入0。
初始情况二：对于第0行，它的含义是屋内没有物品。那么没有任何物品的背包里的价值多少呢？还是没有！所有都是0。