0-1背包 动态规划1
需积分: 0 75 浏览量
2022-08-08
18:51:27
上传
评论
收藏 101KB DOCX 举报
动态规划法解决 0-1 背包问题
【代码】
#include<iostream>
#include<graphics.h>
#include <conio.h>
using namespace std;
#define M 100
void Knapsack(int v[], int w[], int c, int n, int m[M][101])
{
char s[5];
int jmax = min(w[n - 1] - 1, c); //取当中的最小值
for (int j = 0; j <= jmax; j++) //当第n个物品不选时，m[n][j]价值
为0
m[n][j] = 0;
for (int j = w[n - 1]; j <= c; j++) //当第n个物品选择时，m[n][j]
价值为value[n]
m[n][j] = v[n - 1];
//自n-1到2逐层计算各m[i][j] 的值
for (int i = n - 1; i >= 1; i--)
{
jmax = min(w[i - 1] - 1, c);
for (int j = 0; j <= jmax; j++)
m[i][j] = m[i + 1][j];
for (int j = w[i - 1]; j <= c; j++)
m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i - 1]] + v[i -
1]);
}
m[1][c] = m[2][c];
if (c >= w[0]) //处理第一层的边界条件
m[1][c] = max(m[1][c], m[2][c - w[0]] + v[0]);
cout << endl << "构成的m数组为:" << endl;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= c; j++)
printf("%3d ", m[i][j]);
printf("");
}
printf("");
setlinestyle(PS_SOLID,2); //实线2像素的线
//画整个矩形
for (int m = 20; m <= (c + 1) * 40 + 20; m += 40)
评论0