抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

问题描述

Description
一个旅行者有一个最多能装m公斤的背包,现有n件物品,它们的重量分别是w1,w2,w3,…,wn,它们的价值分别为c1,c2,c3,…,cn。若每种物品只有一件,求旅行者能获得的最大总价值。
Input
m,和n(m<=200, n<=30)
接下来共n行每行两个整数wi,ci
Output
最大总价值
Sample Input
10 4
2 1
3 3
4 5
7 9
Sample Output
12

回溯方法

数据定义

1
2
3
4
5
6
7
8
int m;//背包容量
int n;//物品数目
int weight[30];
int value[30];
int MaxValue = 0;//最大价值

int NowWeight = 0;//当前重量
int NowValue = 0;//当前价值

节点

以第i个物品为一个节点,第(i+1)个物品为其儿子节点,左右子树分别表示放入和不放入第i个物品的情况

约束函数

当背包剩余容量不足以放入第i个物品时,其左子树下不可能存在问题的解,因此由剪枝函数终止左子树的遍历

1
2
3
4
5
6
7
8
9
10
//约束函数,返回第i个物品能否放入背包
bool CheckWeight(int i) {
if (NowWeight + weight[i] > m) {
//超重
return false;
} else{
//可以放入
return true;
}
}

回溯法

在遍历i的左子树之前,先判断能否放入第i个物品,如果可以,则尝试放入。当遍历左子树完成后,应当取出第i个物品,并遍历右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Search(int i) {
//i超出范围,说明已经完成了一次DFS
if(i == n){
//更新最大价值
if(NowValue > MaxValue){
MaxValue = NowValue;
}
return;
}
//如果可以放入第i个物品,则尝试遍历
if(CheckWeight(i)){
//尝试放入第i个物品
NowWeight += weight[i];
NowValue += value[i];
//遍历i的子树
Search(i + 1);
//取出第i个物品
NowWeight -= weight[i];
NowValue -= value[i];
}
//这是在没有放入第i个物品的情况下遍历子树
Search(i + 1);
}

完整代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>

using namespace std;

int m;//背包容量
int n;//物品数目
int weight[30];
int value[30];
int MaxValue = 0;//最大价值

int NowWeight = 0;//当前重量
int NowValue = 0;//当前价值

void Search(int i);

int main() {
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &weight[i], &value[i]);
}
Search(0);
printf("%d",MaxValue);
return 0;
}

//约束函数,返回第i个物品能否放入背包
bool CheckWeight(int i) {
if (NowWeight + weight[i] > m) {
//超重
return false;
} else{
//可以放入
return true;
}
}

void Search(int i) {
//i超出范围,说明已经完成了一次DFS
if(i == n){
//更新最大价值
if(NowValue > MaxValue){
MaxValue = NowValue;
}
return;
}
//如果可以放入第i个物品,则尝试遍历
if(CheckWeight(i)){
//尝试放入第i个物品
NowWeight += weight[i];
NowValue += value[i];
//遍历i的子树
Search(i + 1);
//取出第i个物品
NowWeight -= weight[i];
NowValue -= value[i];
}
//这是在没有放入第i个物品的情况下遍历子树
Search(i + 1);
}

动态规划法

问题分解

判断背包当前状态,需要两个参数,第一个是“剩余容量”,可以决定背包还能放下多少物品;第二个是“物品序号”,它决定背包将会被放入哪些物品

有了这两个参数,就能唯一确定背包的状态,因此一定能求出背包在这种状态下能达到的最大价值

状态函数

定义函数GetMaxValue(int capacity, int i),参数是上面提到的状态参数,函数返回值是这种状态下背包能达到的最大价值

状态转移

放入或不放入物品i的最大价值与放入或不放入物品(i+1)的最大价值有关

若放入背包,则背包容量减少,背包价值增加,此时的价值为

1
GetMaxValue(capacity + weight[i],i+1) + value[i]

若不放入背包,则背包容量和价值都不变,直接返回(i+1)时的最大价值

1
GetMaxValue(capacity,i+1)

取两者的较大值

1
2
3
4
5
6
7
8
9
10
11
//返回当前容量为capacity,是否放入物品i时的最大价值
int GetMaxValue(int capacity, int i){
if(i >= n || capacity >= m) return 0;
if(capacity + weight[i] > m){
//放不下物品i,返回是否放入物品(i+1)的最大价值
return GetMaxValue(capacity,i+1);
} else{
//放得下物品i,分别计算放入和不放入物品i的情况,并返回较大值
return Max(GetMaxValue(capacity + weight[i],i+1) + value[i], GetMaxValue(capacity,i+1));
}
}

保存结果

为了避免重复计算,将每次计算的结果保存到数组中,下次如果遇到同样的状态,则可以直接返回结果(在本题中效果不明显)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f[200][30];//记录每次运算的结果

//返回当前容量为capacity,是否放入物品i时的最大价值
int GetMaxValue(int capacity, int i){
if(i >= n || capacity >= m) return 0;
//如果已经计算过这个状态,则直接返回结果
if(f[capacity][i] != -1) return f[capacity][i];
//没有计算过状态,先判断能否放下物品i
if(capacity + weight[i] > m){
//放不下物品i,返回是否放入物品(i+1)的最大价值
f[capacity][i] = GetMaxValue(capacity,i+1);
} else{
//放得下物品i,分别计算放入和不放入物品i的情况,并返回较大值
f[capacity][i] = Max(GetMaxValue(capacity + weight[i],i+1) + value[i], GetMaxValue(capacity,i+1));
}
return f[capacity][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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>

using namespace std;

int m;//背包容量
int n;//物品数目
int weight[30];
int value[30];

int f[200][30];//记录每次运算的结果

int GetMaxValue(int capacity, int i);

int main() {
for(auto & i : f){
for(int & j : i){
j = -1;
}
}
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &weight[i], &value[i]);
}
printf("%d\n", GetMaxValue(0,0));
return 0;
}

int Max(int a,int b){
return a>b?a:b;
}

//返回当前容量为capacity,是否放入物品i时的最大价值
int GetMaxValue(int capacity, int i){
if(i >= n || capacity >= m) return 0;
//如果已经计算过这个状态,则直接返回结果
if(f[capacity][i] != -1) return f[capacity][i];
//没有计算过状态,先判断能否放下物品i
if(capacity + weight[i] > m){
//放不下物品i,返回是否放入物品(i+1)的最大价值
f[capacity][i] = GetMaxValue(capacity,i+1);
} else{
//放得下物品i,分别计算放入和不放入物品i的情况,并返回较大值
f[capacity][i] = Max(GetMaxValue(capacity + weight[i],i+1) + value[i], GetMaxValue(capacity,i+1));
}
return f[capacity][i];
}

评论