0-1背包问题的动态规划
#include <iostream>
#include<string>
#include<iomanip>
using namespace std;
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<<endl; }
动态规划解决算法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 上机...
热门文档