算法设计与分析实验报告

for (j=w[n]; j<=c; j++) {//背包的价值

m[n][j] = v[n]; }

//m(i,j) 背包容量为 j，可选择物品为 i,i+1…n 时 0-1 背包的最优值 for (int i=n-1; i>1; i--) {

jMax = min(w[i] - 1, c); for (int j=0; j<=jMax; j++) { m[i][j] = m[i+1][j]; }

for (j=w[i]; j<=c; j++) {

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]); cout<

template

void TraceBack(Type **m, int *w, int c, int n, int* x)

{//物品装入 x[i]为 1，反之为 0；背包容量 c 减少当前装入物品的重量 for (int i=1; i

if(m[i][c] == m[i+1][c]) x[i] = 0; else {

x[i] = 1; c -= w[i]; } }

x[n] = (m[n][c])? 1:0; }

void main(int argc, char* argv[]) {

int n = 6,c = 20,x[7];

//n 个物品，用 x[7]来记录每个物品是否装入，c 背包容量 int w[7] = {-2, 5, 10, 9, 5, 2, 1}; //每个物品的重量 int v[7] = {-1, 6, 3, -4, 4, 6, 0}; //每个物品的价值 int **ppm = new int*[n+1]; for (int i=0; i

}

Knapsack(v, w, c, n, ppm); TraceBack(ppm, w, c, n, x); for ( i=1; i<=n; i++) { cout<

return; }

（5） 设计一个 O(n2)时间的算法，找出由 n 个数组成的序列的最长单调递增子序 列。（P87 算法分析题 3-1）

（6） 设计算法求解独立任务最优调度问题，并编程实现。 （P79算法实现题 3-1） （7） 设计算法求解石子合并问题编程实现。（P79 实现题 3-3） （8） 设计算法求解数字三角形问题，并编程实现。 （P80题 3-4） #include void main() {

int a[100][100]; int i,j,n;

printf(\输入行数：\ scanf(\ for(i = 1 ; i <= n ; i ++ ) {

printf(\输入第%d 行数：\\n\ for( j =1 ;j <= i; j++) scanf(\ }

for(i = n-1;i>0;i--) for(j = i;j>0;j--) {

a[i][j] += a[i+1][j+1] > a[i+1][j]?a[i+1][j+1] : a[i+1][j]; //a[i][j]选 a[i+1][j+1],a[i+1][j]中最大的 }

printf(\最大路径和是：%d\\n\ return; }

（9） 设计算法求解最小 m 段和问题，并编程实现。 （P81题 3-8）

（10） 设计算法求解最少费用购物问题，并编程实现。（P88 算法实现题 3-14） 注：至少选择其中 3 题完成。 3.主要仪器设备及软件 （1） PC 机

（2） TC、VC++、Java 等任一编程语言 实验四 贪心算法及其应用

（验证型、设计型实验 6 学时） 1.目的要求：

（1） 理解贪心算法的概念和基本要素；

（2） 掌握设计贪心算法的步骤，并编程实现有关问题的求解。 2.实验内容：

（1） 编程实现活动安排问题的求解。 （P91） void sort(int f[],int n) {//结束时间 f[]排序 int temp;

for(int i=1;i

for(int j=0;jf[j+1])

{//结束时间按从早到晚排序 temp=f[j]; f[j]=f[j+1]; f[j+1]=temp; } }

cout<<\排序结果：\ for(int i=0;i

int greedySelector(int s[], int f[], bool A[]) {//活动安排算法

int n=s.length-1,j=1,count=1; A[1]=true;

for(int i=2;i<=n;i++) { if(s[i]>=f[j])

{//若下一活动开始时间晚于上一活动，则下一活动可安排，活动数 count 加 1 A[i]=true; j=i;

count++; }

else A[i]=false; }

return count; }

（2） 设计算法求解会场安排问题，并编程实现。（P108，算法实现题 4-1）。 （3） 编程实现最优装载问题的求解。 （P95） #include \

void sort(int *w,int *t,int n)

{ //按照 weight 的升序进行排序 t[] for(int i=0;i <=n;i++) {

int minweight=w[0];//最小值

for(int j=i;j <=n;j++) {

int temp=j;

for(int k=i;k <=j;k++) {

if(w[k]

t[j]=temp; } } }

void loadling(int x[],int w[],int c,int n) {

int *t=new int[n+1];//指向物品的序号 sort(w,t,n);

for(int i=1;i <=n;i++) {

x[i]=0; }

for(i=1;i<=n&&w[t[i]]<=c;i++) {

x[t[i]]=1; c-=w[i];

cout<<\输出所装载的物品序列号以及它的重量为：\ <

void main() {

int n,c;

cout<<\请输入要装载物品的数量\ cin>>n;

int *w=new int[n+1];//指向物品的重量 int *x=new int[n+1]; for(int i=1;i <=n;i++) {

x[i]=0; }

cout<<\请输入该所能够装载的最大重量：\ cin>>c;

cout<<\请输入装载的物品的重量\