01背包问题动态规划详解及C++代码

0/1背包问题动态规划详解及C++代码

1. 问题描述

给定一个载重量为C的背包有n个物品其重量为wi价值为vi1<=i<=n要求:把物品

装入背包并使包内物品价值最大

2. 问题分析

在0/1背包问题中物体或者被装入背包或者不被装入背包只有两种选择。 循环变量ij意义前i个物品能够装入载重量为j的背包中

数组c意义c[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值

若w[i]>j第i个物品不装入背包

否则若w[i]<=j且第i个物品装入背包后的价值>c[i-1][j]则记录当前最大价值替换为第

i个物品装入背包后的价值

其c++代码如下

#include<iostream>

using namespace std;

void KANPSACK_DP(int c[50][50], int w[50], int v[50], int n, int C)

{

for(int i = 0; i <= C; i ++)

{

c[0][i] = 0;

}

for(int i = 1; i <= n; i ++)

{

c[i][0] = 0;

for(int j = 1; j <= C; j ++)

{

if(w[i] <= j)

{

if(v[i] + c[i - 1][j - w[i]] > c[i - 1][j])

c[i][j] = v[i] + c[i - 1][j - w[i]];

else c[i][j] = c[i - 1][j];

}

else c[i][j] = c[i - 1][j];

}

}

}

void OUTPUT_SACK(int c[50][50], int x[50], int w[50], int n, int C)

{

for(int k = n; k >= 2; k --)

{

if(c[k][C] == c[k-1][C])

x[k] = 0;

else {

x[k] = 1;

C = C - w[k];

}

}

x[1] = c[1][C] ? 1 : 0;

}

int main()

{

int c[50][50];

int w[50],v[50];

int x[50];

int C,n;

cout<<"输入物品的总个数";

cin>>n;

cout<<"输入背包的总容量";

cin>>C;

cout<<"依次输入物品的重量"<<endl; for(int i = 1; i <= n; i ++)

{

cin >> w[i];

}

cout<<"依次输入物品的价值"<<endl; for(int i = 1; i <= n; i ++)

{

cin >> v[i];

}

KANPSACK_DP(c, w, v, n, C); OUTPUT_SACK(c, x, w, n, C);

cout<<"最优解为"<<endl;

for(int i = 1; i <= n; i ++)

{

cout<<x[i]<<" ";

}

cout<<endl<<"最大容量为"<<endl;

cout<<c[n][C]<<endl; system("pause"); return 0;

}

运行结果如下

输入物品的总个数5

输入背包的总容量10

依次输入物品的重量 2 2 6 5 4

依次输入物品的价值 6 3 5 4 6

最优解为 1 1 0 0 1

最大容量为 15

请按任意键继续. . .