l算法设计与分析实验报告—01背包问题.docxVIP

算法设计与分析实验报告—0/1背包问题-【问题描述】给定n种物品和一个背包。物品i的重量是，其价值为，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？【问题分析】0/1背包问题的可形式化描述为：给定C0,0,0,，要求找出n元0/1向量，使得，而且达到最大。因此0/1背包问题是一个特殊的整数规划问题。【算法设计】设0/1背包问题的最优值为m(i,j)，即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：max{m(i+1,j),m(i+1,j-)+} m(i,j)=m(i+1,j)m(n,j)=0 【算法实现】#include iostream.h#includestring.h #includeiomanip.h int min(int w, int c) {int temp; if (w c)temp = w; else temp = c; return temp; } Int max(int w, int c) { int temp; if (w c)temp = w; else temp = c; return temp; }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; cout endl; } int traceback(int x[], int w[], int** m, int c, int n) //回代，求最优解 { out endl 得到的一组最优解如下: 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]; } void main() { int n, c; int **m; cout 欢迎使用0-1背包问题程序 endl; cout 请输入物品个数:; cin n ; cout endl 请输入背包的承重：;cin c;int *v = new int[n+1]; cout endl 请输入每个物品的价值 (v[i]): endl; for(int i = 1; i = n; i++) cin v[i]; int *w = new int[n+1]; cout endl 请输入每个物品的重量 (w[i]): endl; for(int j = 1; j = n; j++) cin w[j]; int *x = new int[n+1]; m = new int* [n+1];//动态的分配二维数组 for(int p = 0; p n+1; p++) m[p] = new int[c+1]; knapsack (v, w, m, c, n); traceback(x, w, m, c, n); }【运行结果】