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地址