习题2数据结构二

1、习题二 算法初步110 设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，Wn。问能否从这n件物品中选择若干件放入到背包中，使得放入物品的重量之和正好为S。如果存在一种符合要求的选择，则称此背包问题有解（真：true），否则此问题无解（假：false）。请写出背包问题的非递归求解算法和程序。算法：考虑到题目只是要求得出背包问题是否有解，所以可以采用深度优先搜索的算法。数组w用来存放n件物品的重量。数组used表示第i件物品是否正放在背包中，若一放入包中则值为1；反之，值为0。建立一个栈bag，用来存放当前尝试放入包中的物品的编号。如果放进一个物品后，现有重量小于s，就进栈

2、，并继续搜索可以放入的物品。如果再放入任何一个物品现有重量都会大于s，那么说明不合适，需要进行回溯，进行相应的出栈操作即可。一直进行到发现问题有解，或者尝试完所有可能的方案。只要找到一组解就调用listbags函数打印出这组解，然后退出。程序中在搜索前把物品重量从小到大进行了排序，这样如果发现第i件物品放入后已经超重，那么i以后的物品就不必考虑了，可以提高效率。为了和题目相照应，也为了减少编程中的麻烦，数组w和used分别使用的是w1wn和used1usedn，w0和used0置零后均未再使用。源代码：#include void listbags(int *,int *,int);/列出找到的

3、第一组解int main (void)int w1000,bag1000,used1000;int s,i,j,k,n,total,temp;printf(请输入背包可以放入的物品重量S: );scanf(%d,&s);printf(请输入物品的件数n: );scanf(%d,&n);w0=0;printf(请输入这%d件物品重量:n,n);for (i=1;i=n;i+)scanf(%d,w+i);for (i=1;in;i+)/按物品重量由小到大排列for (j=i+1;jwj) temp=wi;wi=wj;wj=temp;wn+1=0;bag0=0;/初始化数组for (i=1;i0)w

4、hile ( usedbagk=1 & bagk=n )bagk+;/找到一个还没有放入包中的物品if ( (bagk=n) & (total+wbagk=s) )if (total+wbagk=s) printf(True! 此背包问题有解!n其中一组解如下:nS=%d=,s);listbags(bag,w,k);return(1);else/还未达到总重量total=total+wbagk;usedbagk=1;k+;bagk=bagk-1+1;else/超重，需要回溯bagk=0;k-;total=total-wbagk;usedbagk=0;bagk+;printf(False! 此背包问题无解!n);return(0);void listbags(int *bag,int *w,int k)int i;for (i=1;ik;i+)