Contents
  1. 1. 题目描述
  2. 2. 二维数组存储最优解
  3. 3. 一维数组存储最优解
  4. 4. 这是构造最优解的算法 ,即放入哪些物品。

关于0-1背包的两种解法

题目描述

背包容量c=10
物品数量n=5
输入五个物品的重量w[i]和价值v[i]
求最大价值。

二维数组存储最优解

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<algorithm>
using namespace std;
int m[1000][1000];
void knapsack(int *v,int *w,int n,int c)
{
int jmax=min(w[n]-1,c);
for(int j=0;j<=jmax;j++)m[n][j]=0;
for(int j=w[n];j<=c;j++)m[n][j]=v[n];
for(int i=n-1;i>1;i--)
{
int jmax=min(w[i]-1,c);
for(int j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(int j=w[i];j<=c;j++)
m[i][j]=max(m[i+1][j],m[i+1][j-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]);
}
int main()
{
int c=10; //背包容量
int n=5; //物品数目
int v[10]={0},w[10]={0};//v[]价值,w[]重量
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
knapsack(v,w,n,c);
cout<<m[1][c];
}

一维数组存储最优解

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int m[1000];
int main()
{
int c=10;
int n=5;
int v[10]={0},w[10]={0};
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++)
for(int j=c;j>=w[i];j--)
m[j]=max(m[j],m[j-w[i]]+v[i]);
cout<<m[c];
}

这是构造最优解的算法 ,即放入哪些物品。

1
2
3
4
5
6
7
8
9
10
11
12
void traceback(int **m,int *w,int c,int n,int *x)
{
for(int i=1;i<n;i++) //1--放入 0--不放入
if(m[i][c]==m[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
x[n]=(m[n][c])?1:c;
}
Contents
  1. 1. 题目描述
  2. 2. 二维数组存储最优解
  3. 3. 一维数组存储最优解
  4. 4. 这是构造最优解的算法 ,即放入哪些物品。