背包问题

发表于   |   分类于   |  

01背包问题

问题描述

有N件物体，体积为v1、v2…vN，价值为w1、w2…wN。
现在有一个容量为V的包，从N件物体中选择若干件放进包里，使得包里物体的总价值最大。

基本思路

利用动态规划，建立(N+1)*(V+1)的矩阵F[N+1][V+1]，F[i][j]表示在前i个物体中取若干个放入剩余容量为j的背包得到的最大的价值。于是有：

1
F[i][j] = max(F[i-1][j], F[i-1][j-v[i]]+w[i])

需要注意的是，矩阵第一行第一列为0，表示没有物体或者没有剩余空间时价值都是0。实际上F[i-1][j]表示没有放进第i个物体，F[i-1][j-v[i]]+w[i]表示放进了第i个物体时的价值。

伪代码

1
2
3
4
5
6
7
8
9
10
11
F[0][] <- 0
F[][0] <- 0
for i = 1...N
	for j = 1...V
		F[i][j] = F[i - 1][j]
		if (j >= v[i]) //能放进第i个物体
			F[i][j] = max(F[i][j], F[i - 1][j - v[i]] + w[i])
		end
	end
end
F[N][V]即为所求

二维01背包问题

类似于01背包问题，有N件物体，消耗两种属性，背包也有两种待消耗属性。求总价值最大。

伪代码

类似于01背包问题，c1, c2是物体的两种属性，v1和v2是背包的两种属性。建立F[v1+1][v2+1]，F[i][j]表示背包两种属性为i和j时可放下的最大价值。

1
2
3
4
5
6
7
8
F[0][0] = 0
for i = 1...N
	for j = v1...c1[i] // decrease
		for k = v2...c2[i] // decrease
			F[j][k] = max(F[j][k], F[j - c1[i]][k - c2[i]] + w[i])
		end
	end
end

实例

宠物小精灵之收服

描述
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入
输入数据的第一行包含三个整数：N(0 < N < 1000)，M(0 < M < 500)，K(0 < K < 100)，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

代码

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
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
   	int v1, v2, N;
   	int c1[100], c2[100], f[1000][500] = {0};
   	cin >> v1 >> v2 >> N;
   	for (int i = 1; i <= N; i++){
       	cin >> c1[i] >> c2[i];
   	}
   	f[0][0] = 0;
   	for (int i = 1; i <= N; i++){
      	for (int j = v1; j >= c1[i]; j--){
         	for (int k = v2; k >= c2[i]; k--){
             	f[j][k] = max(f[j][k], f[j - c1[i]][k - c2[i]] + 1);
         	}
   		}
    }
    for (int k = 0; k <= v2; k++){
      	if (f[v1][k] == f[v1][v2]){
         	cout << f[v1][v2] << " " << v2 - k << endl;
         	break;
      	}
    }
   	return 0;
}