算法分析与设计 0-1背包问题

　　　问题可以描述为：给定一组共n个物品，每种物品都有自己的重量wi,i=1~n和价值vi,i=1~n，在限定的总重量（背包的容量C）内，如何选择才能使得选择物品的总价值之和最高。选择最优的物品子集放置于给定背包中，最优子集对应n元解向量(x1,…xn),　　　为方便调试，采用文件输入，标准输出（或文件输出也可）的形式。数据输入的格式如下：每组测试数据　　　包含n+1行，第1行为C和n，表示背包容量为C且有n个物品，接下来n行为这n个物品的重量wi和价值vi。背包容量和物品重量都为整数。n,C,wi,vi范围如上所述。输出两行。第一行为所选物品的最大价值之和，第二行后为装入背包的物品所对