算法设计与分析参考答案

/* 问题及所用实例描述： 容量C=10, 物品个数n=5, 第1到第5个物品重量分别为 w[5]={2,2,6,5,4},价值分别为v[5]={6,3,5,4,6} table[i][j]的含义为，背包容量为j，可选择物品还剩下i、i+1、...n 公式:table[i][j]=max{ table[i+1][j], table[ i+1][j-w[i] ]+v[i] } **/ #include<iostream> using namespace std; #define min(x,y) ( (x)<(y) ? (x):(y) ) //演示宏定义完成小函数功能,注意括号多是有必要的 int max(int x,int y){ int z; x>y? z=x:x=y; return x;} int knapsack(int c,int n,int* w,int* v); int main() { int c=10,n=5; int w[6]={0,2,2,6,5,4}; //再次说明，和其他程序一样，w[0]未使用! //后面的代码下标从w[1]到w[5] int v[6]={0,6,3,5,4,6}; cout << knapsack(c,n,w,v); return 0; } int knapsack(int c,int n,int* w,int* v){ //动态分配2维数组即要填的表 int* *table=new int*[n+1]; for(int cols=0;cols<=n;cols++) table[cols]=new int[n+1]; //初始化table的第n行，也就是只有第n个物品可以考虑的情况 //（即原子问题，再次啰唆下，画出递归树很容易看出怎么初始化） if (w[n]<c) //最后一个物品放得下则填入其价值 { for(int j=w[n];j<=c;j++) //比如这里最后一个即第5个物品重量为4，从表的第5行第4列起都可以放入 table[n][j]=v[n]; for(j=0;j<w[n];j++) //第5行前面的1、2、3列补0 table[n][j]=0; } else //由于第n个物品超出背包容量，第n行怎么也放不下第n个，全0 { for(int j=0;j<=n;j++) table[n][j]=0; } //套公式，注意这里的小技巧jMax简化代码，上面的初始化也可以如此 int jMax; for(int i=n-1;i>=1;i--){ // w[i]-1 < c? jmax=w[i]-1 : jmax=c; jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) table[i][j]=table[i+1][j]; for(j=w[i];j<=c;j++) table[i][j]=max(table[i+1][j],table[i+1][j-w[i]]+v[i]); } int result=table[1][c]; //结果在table[1][c]处 //注意！！下面这段注释掉的代码运行会出错，为什么？请同学们自己通过调试解决问题 //这样你对指针错误就有经验了。提示: 当然是释放了不该释放的内存，数组越界之类， //检查前面的代码 /* for(cols=0;cols<=n;cols++) delete []table[cols]; delete []table; */ return result; }