资 源 简 介
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价值为最大。
在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能讲物品i装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。该算法中,矩阵c的大小为(m+1)×(n+1),物体的重量、价值和解向量大小都等于物体个数n,故该算法的空间复杂度为O(nm)。对物体重量、价值的初始化(算法实现略)所需时间都为n,解向量和矩阵第0行初始化时间为n,矩阵第0列初始化时间为m,对矩阵c的计算所需时间为n×m,解向量X的确定时间为n,故整个算法的时间复杂度为O(nm)。
