算法设计与分析综合设计性实验报告

0-1背包问题的多种算法设计与分析 0-1背包问题是一例典型的组合优化的NP完全问题。问题可以描述为：给定一组共n个物品，每种物品都有自己的重量wi, i=1~n和价值vi, i=1~n，在限定的总重量（背包的容量C）内，如何选择才能使得选择物品的总价值之和最高。选择最优的物品子集放置于给定背包中，最优子集对应n元解向量(x1,…xn), xi∈{0或1}，因此命名为0-1背包问题。