算法分析與复杂性理论实验报告动态规划.docxVIP

深 圳 大 学 实 验 报 告课程名称： 算法分析与复杂性理论 实验名称： 实验四 动态规划 学院： 计算机与软件学院 专业： 软件工程 报告人： 文成 学号： 2150230509 班级： 学术型 同组人： 无 指导教师： 杨烜 实验时间： 2015/11/5——2015/11/18 实验报告提交时间： 2015/11/18 教务处制实验目的与实验内容实验目的：（1）?掌握动态规划算法设计思想。（2）?掌握背包问题的动态规划解法。实验内容：1. 编写背包问题的动态规划求解代码。2．背包容量为W，物品个数为n，随机产生n个物品的体积（物品的体积不可大于W）与价值，求解该实例的最优解。3.?分别针对以下情况求解第一组：（n=10,W=10），（n=10,W=20），（n=10,W=30）第二组：（n=20,W=10），（n=20,W=20），（n=20,W=30）第三组：（n=30,W=10），（n=30,W=20），（n=30,W=30）4.?画出三组实验的时间效率的折线图，其中x轴是W的值，y轴是所花费的时间，用不同的颜色表示不同n所花费的时间。二．实验步骤与结果背包问题的问题描述：给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？背包问题的算法思想：考虑一个由前i个物品（1=i=n）定义的实例，物品的重量分别为w1，…，w2、价值分别为v1，…，vi，背包的承重量为j（1=j=w）。设v[i,j]为该实例的最优解的物品总价值，也就是说，是能够放进承重量为j的背包中的前i个物品中最有价值子集的总价值。可以把前i个物品中能够放进承重量为j的背包中的子集分成两个类别：包括第i个物品的子集和不包括第i个物品的子集。根据定义，在不包括第i个物品的子集中，最优子集的价值是V[i-1,j]。在包括第i个物品的子集中（因此，j-wi=0），最优子集是由该物品和前i-1个物品中能够放进承重量为j-wi的背包的最优子集组成。这种最优子集的总价值等于vi+V[i-1,j-wi]。因此，在前i个物品中最优解得总价值等于这两个价值中的最大值。当然，如果第i个物品不能放进背包，从前i个物品中选出的最优子集的总价值等于从前i-1个物品中选出的最优子集的总价值。这个结果导致了下面的这个递推关系式：初始条件：当i,j0时，V为了计算第i行第j列的单元格[i,j]，我们拿前一行同一列的单元格与vi加上前一行左边wi列的单元格的和做比较，计算出两者的较大值。代码实现;//后面有个例子//说白了做法就写出最优值矩阵。void knapsack(int v[], int w[], int** m, int c, int n)//求最优值 { int jmax = min(w[n]-1, c); for (int j = 0; j = jmax; j++) m[n][j] = 0; for (int jj = w[n]; jj = c; jj++) m[n][jj] = v[n]; 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(int jj = w[i]; jj = c; jj++) m[i][jj] = max(m[i+1][jj], m[i+1][jj-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 endl 最优值： m[1][c] endl; coutendl; coutendl; } int traceback(int x[], int w[], int** m, int c, int n) //回代，求最优解 { coutendl得到的一组最优解如下: endl; for(int i = 1; i n; 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; for(int y = 1; y = n; y++) cout x[y] \t; cout endl;return x[n]; }一个例子:用课本上的一个例子进行测试：承重量W=5。物品重量价值（美元）1212211033204215分析：说白了最简单的做