计算机算法设计与分析.docx

《计算机算法设计与分析.docx》由会员分享，可在线阅读，更多相关《计算机算法设计与分析.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算法设计与分析 课内实验 学号： 班级：智能1004班 姓名：王维 指导老师：陈琳1.0-1背包问题#includeint n,c,bestp;/物品的个数，背包的容量，最大价值int p10000,w10000,x10000,bestx10000;/物品的价值，物品的重量，xi暂存物品的选中情况,物品的选中情况void Backtrack(int i,int cp,int cw) /cw当前包内物品重量，cp当前包内物品价值 int j; if(in)/回溯结束 if(cpbestp) bestp=cp; for(i=0;i=n;i+) bestxi=xi; else for(j=0;

2、j=1;j+) xi=j; if(cw+xi*wi=c) cw+=wi*xi; cp+=pi*xi; Backtrack(i+1,cp,cw); cw-=wi*xi; cp-=pi*xi; int main() int i; bestp=0; printf(请输入背包最大容量:n); scanf(%d,&c); printf(请输入物品个数:n); scanf(%d,&n); printf(请依次输入物品的重量:n); for(i=1;i=n;i+) scanf(%d,&wi); printf(请依次输入物品的价值:n); for(i=1;i=n;i+) scanf(%d,&pi); Back

3、track(1,0,0); printf(最大价值为:n); printf(%dn,bestp); printf(被选中的物品依次是(0表示未选中，1表示选中)n); for(i=1;i=n;i+) printf(%d ,bestxi); printf(n);return 0;2.n后子集数#include #include #include using namespace std;bool Place(int t, int x)for(int j=1; j n)sum +;for(int m=1;m=n;m+) /打印排列位置printf(%d ,xm);printf(n);elsefor(

4、int i=t; i=n; i+) /假则返 回溯法xt=i;if(Place(t, x)Backtrack(t+1, n, x, sum); /回溯法 排列void main()int n, sum(0); /n是表示有几个皇后，sum表示可行解的数量printf(请输入几个皇后： );scanf(%d,&n);int *x = new int n+1;for(int i=0; i=n; i+)xi = i;Backtrack(1, n, x, sum);printf(共有%d种n,sum);getchar();3、n后问题（非递归算法）#include stdafx.h#include #

5、include #include #include using namespace std;bool Place(int t, int x)for(int j=1; j0)xk+=1;while(xk=n)&!(Place(k, x)xk+=1;if(xk=n)if(k=n)sum+;elsek+;xk=0;elsek-;void main()int n, sum(0); /n是表示有几个皇后，sum表示可行解的数量printf(请输入几个皇后： );scanf(%d,&n);int *x = new int n+1;for(int i=0; i=n; i+)xi = i;Backtrack(n, x, sum);printf(共有%d种n,sum);while(1);