备战 ACM 资料习题1．0-1 背包问题在 0 / 1 背包问题中,需对容量为 c 的背包进行装载.从 n 个物品中选取装入背包的物品，每件物品 i 的重量为 wi ，价值为 pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。 程序如下:＃include 〈stdio.h>void readdata(）；void search(int）;void checkmax(）；void printresult（）；int c=35， n=10； //c： 背包容量；n:物品数int w［10]， v[10］； //w［i]、v[i]:第 i 件物品的重量和价值int a[10］， max； //a 数组存放当前解各物品选取情况；max：记录最大价值 //a［i]=0 表示不选第 i 件物品，a［i］=1 表示选第 i 件物品int main()｛readdata（); //读入数据search(0）; //递归搜索printresult（）;}void search(int m）｛if（m>=n）checkmax(); //检查当前解是否是可行解,若是则把它的价值与 max 比较else{a［m］=0; //不选第 m 件物品search(m+1); //递归搜索下一件物品a［m]=1； //不选第 m 件物品search（m+1）； //递归搜索下一件物品}}void checkmax(）{int i， weight=0， value=0;for（i=0;i〈n;i++){if(a[i]==1) //假如选取了该物品{weight = weight + w［i］； //累加重量value = value + v[i］; //累加价值｝}if(weight<=c） //若为可行解if(value>max) //且价值大于 maxmax=value； //替换 max}void readdata（）｛int i;for(i=0；i
