0-1背包问题的动态规划
int traceback(int x[], int w[], int** m, int c, int n) //回代,求最优解 {
cout << 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];
}
int main()
{
int n, c;
int **m;
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);
}
动态规划解决算法0-1背包问题实验报告(含源代码)_计算机软件及应用_IT/计算机_专业资料。1.设计一个O(n^2)时间的算法,找出由n个数组成的序列的最长单调递增...
解0-1背包问题的动态规划算法_计算机软件及应用_IT/计算机_专业资料。本文...[2] C语言程序设计:潭浩强编著。 [3] 计算机算法基础:第二版/余祥宣等编著...
动态规划算法:0-1背包问题_工学_高等教育_教育专区。动态规划算法:0-1背包... 3页 1下载券 算法设计 0-1背包问题用... 8页 2下载券喜欢此文档的还...
基于Visual C++的0-1背包问题的动态规划算法_专业资料。0-1背包问题是经典的NP问题.本文对0-1背包问题的动态规划算法进行了分析,用Visual C++实现该算法....
的问题 1.4 最优性原理 1.5 无后效性原则 1.6 动态规划法的设计思想 1...子问题n 填表 原问题的解图2 动态规划法的求解过程 动态规划算法的基本步骤一...
的问题 1.4 最优性原理 1.5 无后效性原则 1.6 动态规划法的设计思想 1...子问题n 填表 原问题的解图2 动态规划法的求解过程 动态规划算法的基本步骤一...
0-1背包问题 44页 免费 算法合集之《动态规划的... 35页 免费 算法合集之...的问题 1.4 最优性原理 1.5 无后效性原则 1.6 动态规划法的设计思想 1...
实验3. 基于动态规划方法求解 0-1 背包问题 实验内容本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法 描述、算法正确性证明、算法分析...
关键词:动态规划0-1背包例算法设计 1/2 相关文档推荐 动态规划法解0-1背包... 如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...
利用动态规划求解0-1背包问题_计算机软件及应用_IT/计算机_专业资料。算法分析与设计 实验报告 班级: 学号: 姓名: 0209404 班 020940410 杨洲 2011-11-7 上机...
热门文档