安 徽 工 业 大 学专 业：班 级：姓 名：学 号：实验一：回溯法完成 0-1背包问题代码如下：#include stdafx.h#include#include#include#includeusing namespace std;templateclass Knappublic:friend void Init();friend void Knapsack();friend void Backtrack(int i);friend float Bound(int i);bool operator a)constif(flvoid Sort(Knap *li,int n)int i,j,k; Knap minl;for(i=1;i *bag=NULL;int cp=0,cw=0;int bestp=0;using namespace jie;void Init()int i=0;coutn; coutc; cout n;x=new intn;coutbagi.w;coutbagi.v;for(i=0;i=n) /到达叶节点bestp=cp; /更新最优价值return;if(cw+bagi.wbestp)/进入右子树bagi.flag=0; Backtrack(i+1);/计算当前节点处的上界float Bound(int i)int cleft = c-cw; /剩余容量float b = cp;while (i #include #include void MergeSort(int *data,int x,int y,int *temp) int p,q,m,i=x;if (y-x1) m = x+(y-x)/2;p = x; q = m; MergeSort(data,x,m,temp);MergeSort(data,m,y,temp);while(p=y|(ppif (qp) temp = datap,datap = dataq,dataq =temp;p+; while(qp if (p9/但是记住规则：每一行最开始部分的空格减少了 k个，那么当 t为个位数时输出 k+2个空格else if(t99/其他 t的情况依次递减就行了else if(t999/如，我在此设计的每行开头部分减少 3个空格，那么 t9&t9999void scan(int row)/杨辉三角扫描输出函数int t = 0 ;if (row10)/当行数大于 10行时，应该将窗口尺寸该大到 150,以保证杨辉三角正常显示，这是一条 dos命令，使用 system函数推送执行的system(mode con cols=150 lines=150);for (int n=0; nrow; n+)print_spack(3*(row-n),1);/后面第二个参数传了一个非零参数，是因为告诉函数要直接输出 3*(row-n)个空格for (int m=0; m=n; m+)/输出中间元素printf(%d,t = Try(n,m);/递归调用获得当前第 n行，第 m个元素的值，输出同时赋值给 tprint_spack(t);/这儿没有传第二个参数是告诉函数，需要判断 t参数的位数来决定输出的空格printf(n);/每行结束后打印一个回车void main()int x = 0;while (true)printf(n递归实现杨辉三角！n 本程序不能大于 20行。n请输入杨辉三角的行数：（输入-1 结束程序）);scanf(%d,/输入行数if (x=-1)exit(0);system(cls);scan(x);/扫描输出运行结果：