? 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 ? 具体算法可描述如下：
void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort(n,v,w); int i;
for (i=1;i<=n;i++) x[i]=0; float c=M;
for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; }
if (i<=n) x[i]=c/w[i]; }
（2）动态规划法 O(nc)
m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。
j?wim(i?1,j),m(i?1,j?wi)?vi}?max{m(i,j)??0?j?wim(i?1,j)?j?wn?vm(n,j)??n?00?j?wn
void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c);
for (j=0;j<=jMax;j++) /*m(n,j)=0 0= for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=w[n]*/ m[n][j]=v[n]; for (i=n-1;i>1;i--) { int jMax=min(w[i]-1,c); for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0= for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } （3）回溯法 O(2n) cw:当前重量 cp:当前价值 bestp：当前最优值 void backtrack(int i) //回溯法 i初值1 { if(i > n) //到达叶结点 { bestp = cp; return; } if(cw + w[i] <= c) //搜索左子树 { cw += w[i]; cp += p[i]; backtrack(i+1); cw -= w[i]; cp -= p[i]; } if(Bound(i+1)>bestp) //搜索右子树 backtrack(i+1); } 七、算法设计题（本题10分） 为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。 具体算法如下： 输入s, n; while（ s > 0 ） { i=1; //从串首开始找 while (i < length(n)) && (n[i] delete(n,i,1); //删除字符串n的第i个字符 s--; } while (length(n)>1)&& (n[1]=?0?) delete(n,1,1); //删去串首可能产生的无用零 输出n; 三、算法填空 1.背包问题的贪心算法 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; for (i=1;i<=n;i++) x[i]=0; float c=M; for (i=1;i<=n;i++) { if (w[i]>c) break; x[i]=1; c - =w[i]; } if (i<=n) x[i]=c/w[i]; } 2.最大子段和: 动态规划算法 int MaxSum(int n, int a[]) { int sum=0, b=0； //sum存储当前最大的b[j], b存储b[j] for(int j=1； j<=n； j++) { if (b>0) b+= a[j] ； else b=a[i]; ； //一旦某个区段和为负，则从下一个位置累和 if(b>sum) sum=b; } return sum； } 3.快速排序 template void QuickSort (Type a[], int p, int r) { if (p int q=Partition(a,p,r); QuickSort (a,p,q-1); //对左半段排序 QuickSort (a,q+1,r); //对右半段排序 } } 4.排列问题 Template void perm(Type list[], int k, int m ) { //产生[list[k:m]的所有排列 if(k==m) { //只剩下一个元素 for (int i=0;i<=m;i++) cout< else //还有多个元素待排列，递归产生排列 for (int i=k; i<=m; i++) { swap(list[k]，list[i]); perm(list,k+1;m); swap(list[k],list[i]); } } 5.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。 据此容易设计出二分搜索算法： template int BinarySearch(Type a[], const Type& x, int l, int r) { while (l<=r ){ int m = ((l+r)/2); if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; } return -1; } 6、合并排序描述如下： template void Mergesort(Type a[ ], int left, int right) { if (left int i=( left+right)/2; Mergesort(a, left, i ); Mergesort(a, i+1, right); Merge(a,b, left,i,right);//合并到数组b Copy(a,b, left,right ); //复制到数组a } } 7、以下是计算xm的值的过程 int power ( x, m ) {//计算xm的值并返回。 y=( 1 );i=m; While(i- - >0) y=y*x; (return y) ; } 四、问答题 1.用计算机求解问题的步骤： 1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制