C语言课程设计背包问题的求解报告.docVIP

1 问题要求及任务描述 1.1 题目要求 背包问题的求解 问题描述： 假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解： （1，4，3，2） （1，4，5） （8，2） （3，5，2）。2.2 拟采用解决问题的方法 利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，2.3 主要算法和处理流程图 利用多重循环结构来寻找正确的解。 3 程序实现 3.1 程序实现时应考虑的问题 应尽可能写得简洁一些，好让他人在看的时候可以看得懂。 3.2 主要源代码及说明 #includestdio.h void search(int w[],int n,int t)/*寻找解的函数*/ { int b[50];/*用数组b存放符合题目的解*/ int i,k,sum,start; for(k=0;k50;k++)/*把存放符合题目的解的数组清零*/ { b[k]=0; } for(start=0;startn;start++) { k=0; sum=0;/*每一次外循环时把和清零*/ for(i=start;in;i++) { sum=sum+w[i]; b[k]=w[i]; if (sum==t) { for(k=0;b[k]!=0;k++)/*若总和等于包的最大容量就输出符合的解*/ { printf(%d ,b[k]); } printf(\n); } else if (sum!=t) { if (sumt)/*若总和大于包的容量，则去掉这一次放入的物品*/ { sum=sum-w[i]; b[k]=0; k--; } else if (i==n-1)/*若在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，将它取出弃之一边*/ { b[k-1]=0; sum=sum-w[i]-w[k-1]; i=k; k--; } k++; } }/*内循环结束*/ }/*外循环结束*/ } main()/*主函数*/ { int i,j; int w[100],n,t; printf(题目：背包问题的求解\n); printf(请输入总体积\n); scanf(%d,t); printf(请输入物品数目\n); scanf(%d,n); printf(请输入各物品重量\n); for(i=0;in;i++)/*输入各物品的重量*/ { scanf(%d,w[i]); } printf(解法有:\n); search(w,n,t); } 4 测试 4.1 测试结果及分析 5 小结 5.1本问题解决方法及程序实现小结 程序的缺点是：尚未可以找出所有正确的解，以及会多找出一些错误的解。此程序是利用多重循环结构来求解。 5.2 尚未解决的问题及下一步工作思路 程序尚未可以找出所有正确的解，以及会多找出一些错误的解。 6 参考文献 无。 东莞理工学院课程设计 1