算法分析(实验六)

系部 计算机系 班级 课程名称 实验名称 源程序： #include int n,c,bestp;//物品的个数，背包的容量，最大价值 int p[10000],w[10000],x[10000],bestx[10000];//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况 void Backtrack(int i,int cp,int cw) { //cw当前包内物品重量，cp当前包内物品价值 int j; if(i>n)//回溯结束 { if(cp>bestp) { bestp=cp; for(i=0;i<=n;i++) bestx[i]=x[i]; } } else for(j=0;j<=1;j++) { x[i]=j; if(cw+x[i]*w[i]<=c) { cw+=w[i]*x[i]; cp+=p[i]*x[i]; Backtrack(i+1,cp,cw); cw-=w[i]*x[i]; cp-=p[i]*x[i]; B140504 学号 B14050427 姓名 鲍帅旗 实验日期 2016.6.3 算法分析与设计 成绩 回溯法解决背包问题 } } } int main() { int i; bestp=0; printf(\"请输入背包最大容量:\"); scanf(\"%d\ printf(\"请输入物品个数:\"); scanf(\"%d\ printf(\"请依次输入物品的重量:\"); for(i=1;i<=n;i++) scanf(\"%d\ printf(\"请依次输入物品的价值:\"); for(i=1;i<=n;i++) scanf(\"%d\ Backtrack(1,0,0); printf(\"最大价值为:\"); printf(\"%d\\n\ printf(\"被选中的物品依次是(0表示未选中，1表示选中)\"); for(i=1;i<=n;i++) printf(\"%d \ printf(\"\\n\"); return 0; }