备战 ACM 资料习题1．0-1 背包问题在 0 / 1 背包问题中，需对容量为 c 的背包进行装载。从 n 个物品中选取装入背包的物品，每件物品 i 的重量为 wi ，价值为 pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 程序如下：#include 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比较 Word 资料 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;imax) //且价值大于 maxmax=value; //替换 max}void readdata(){int i;for(i=0;i
