01背包问题描述：
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi，背包的容量为C。问应 该如何选择装入背包的物品，使得转入背包的物品的总价值为最大？？
先将问题实体化：
有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
通过将问题实例化，便于分析问题。
首先，假设现在只有物品e，一个承重为1的背包，那么此时的背包装好后最大价值为0，因为e的重量大于1。好，现在背包承重不变，又来了个物品的d，此时背包价值依旧为0，又来了c，b，a，价值还是0。当物品遍历（遍历用词不够严谨）完后，我们使背包重量+1，再次从e~a遍历物品，计算其背包的最大价值，直到背包的承重到10，有a~e五个物品时。此时最大价值为15，放入背包的物品为：a，b，e。由此，我们可以得到下图：
根据我们的实际操作，此图是从左到右，自底向上生成的。
这样问题的状态转移方程就很好理解了：f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值，
Pi表示第i件物品的价值，Wi表示第i件物品的重量。
C实现：github地址
网友评论