开餐馆问题

发表于 | Edited on | 分类于 | 次阅读

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, … mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

解题思路

思路一：将问题专为话最长递增子序列的问题。

- 假设dp[i]表示选定了第i个位置开餐馆的最大收益，此时递推公式为：
F[i] = max(F[i], F[t]+profit[i]); 其中1<t<i 同时t和i之间的距离大于k

在这种思路下，代码如下:

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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

// pos[i]表示第i个餐馆的位置， profit[j]表示第j个位置开餐馆的利润
int solution1(vector<int>& pos, vector<int>& profit, int k) {
	vector<int> F(profit);
	int ans = profit[1];
	for (int i = 1; i < pos.size(); ++i) {
		for (int j = 1; j <= i - 1; ++j) {
			if (pos[i] - pos[j] > k)
				F[i] = max(F[i], F[j] + profit[i]);

		}
		ans = max(ans, F[i]);
	}
	return ans;
}

int main() {
	int G;
	while (scanf("%d", &G) != EOF) {
		while (0 < G--) {
			int n, k;
			scanf("%d %d", &n, &k);
			vector<int> pos(n + 1, 0);
			for (int i = 1; i <= n; ++i) {
				scanf("%d", &pos[i]);
			}
			vector<int> profit(n + 1, 0);
			for (int i = 1; i <= n; ++i)
				scanf("%d", &profit[i]);
			printf("%d\n", solution1(pos, profit, k));
		}
	}
}

思路二：将问题转化为0-1背包问题

- 假设dp[i][j]在长度为pos[j]的范围内，考虑前i个餐馆的最大利润，此时递推公式如下：

dp[i][j] = max(dp[i-1][j], dp[i-1][pos[i]-k-1]+profit[i]);

上述递推公式虽然涉及到了i和j，但是对背包问题经过空间优化，可以使用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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int solution2(vector<int>& pos, vector<int>& profit, int k) {
	// F[i][j] 表示考虑前i个餐馆，前j个位置的最大距离
	// F[i] = max{F[k]+profit[i]};
	vector<int> dp(pos.size(), 0);
	for (int i = 1; i < pos.size(); ++i) {
		for (int j = pos.size()-1; j>=i; --j) {
			if (pos[j] >= pos[i]){
				int index = i;
				while(pos[i] - pos[index] <= k&&index >0)
					--index;
				dp[j] = max(dp[j], dp[index] + profit[i]);
			}
		}
	
	}
	return dp[pos.size() - 1];
}

int main() {
	int G;
	while (scanf("%d", &G) != EOF) {
		while (0 < G--) {
			int n, k;
			scanf("%d %d", &n, &k);
			vector<int> pos(n + 1, 0);
			for (int i = 1; i <= n; ++i) {
				scanf("%d", &pos[i]);
			}
			vector<int> profit(n + 1, 0);
			for (int i = 1; i <= n; ++i)
				scanf("%d", &profit[i]);
			printf("%d\n", solution2(pos, profit, k));
		}
	}
}

时间复杂度分析

  • 第一种思路的方法，选定一个i的时候，需要向前遍历距离大于k的位置，因此时间复杂度为O(n^2)$。
  • 第二种思路的方法，看起来有三个循环，但是实际上第二个for循环和while循环加起来总共是O(n)的时间复杂度，所以时间复杂度也是O(n^2)。