问题描述
John 有两个孩子，在 John病逝后，留下了一组价值不一定相同的魔卡， 现在要求你设计一种策略，帮John的经管人将John的这些遗产分给他的两个孩子，使得他们获得的遗产差异最小（每张魔卡不能分拆）。
假设已知某股票连续若干天的股价，并且如何时候你手上只能由一支股票，即如果你要买入就得先将手上股票卖出，设计一个算法来计算你所能获取的最大利润。你最多可以完成 k笔交易。也就是说，你最多可以买k 次，卖 k 次。
1
2
3
4
| 输入：k = 2, prices = [3,2,7,5,1,4]
输出：8
7-2 + 4-1
|
解题思路
T1
这是一个贪心算法问题还是一个动规问题呢？
在思考这道题的时候，我犯了过于经验主义的错误。因为和之前遇见的题目有过类似的，觉得是贪心，所以没有多去求证，就框框把代码写完了，其实贪心并不能得到全局最优解(😁十分感谢看到我博客的同班同学的提醒)
贪心的思路是：
- 将所有的魔卡按照价值从大到小排序。
- 从价值最高的魔卡开始，依次分配给两个孩子中当前遗产较少的那个孩子。
- 重复步骤2直到所有的魔卡都被分配完毕。
这样是有问题的，直接举反例，当 N = 2 时 cards = [5, 3, 2, 2, 2, 2] 贪心求解ans = 2。然而正确的最优解应该为0，两个孩子分别[5, 3]和[2, 2, 2, 2]
因此，正确解法为动态规划。
动态规划的思路是：
- 求取所有卡牌价值之和
sum
- 然后转换成01背包问题，商品的价值和重量都等于卡牌的价值，背包的上限
m = sum/2，尽可能的往这个背包里装商品使其价值最大，即最靠近sum/2。求得此时的最大价值dp[n][sum/2]为ans。
- 最后此问题的解为
sum - 2*ans。
T2
那么这道题到底是贪心还是动规呢？
我们知道动规有一道经典例题，就是非升子序列，不觉得这题有几分相似，都是必须从前往后求最优。其实要证明贪心算法不行只要举个反例就行了。
于是就根据经验按照动规的思路来思考。考虑使用二维数组dp[i][j]，代表当前状态的最大利润，i代表当前是第i次买卖，j代表当前是第j天。
对于每个状态都有买和不买。为什么是买和不买呢，不是还有卖吗？其实是赚钱和不赚钱这两种选择，赚钱是卖与买之间的差值。所以这道题比一般的动态规划要更复杂些。
对于每一次买卖，必须有买才有卖，先用maxDiff包括因为买股票亏的钱，一开始由于没有股票，就等于-prices[1]。这个亏的钱也完全不是负数亏的钱，还要包括之前(上一次买卖)因为赚钱累计的成本，这个maxDiff就是代表本次买卖状态下的累计成本(比较难理解)。所以$$maxDiff = max(maxDiff, dp[i-1][j] - prices[j])$$
对于每一天，都有去赚钱和不赚钱。不赚钱利润等于昨天的利润，去赚钱的利润等于累计成本maxDiff加上prices[j]，因此$$dp[i][j] = max(dp[i][j-1], prices[j] + maxDiff)$$
在样例下，dp运算结果如下所示。
| prices |
3 |
2 |
7 |
5 |
1 |
4 |
| dp[1][j] |
0 |
0 |
5 |
5 |
5 |
5 |
| dp[2][j] |
0 |
0 |
5 |
5 |
5 |
8 |
这个dp[k][n]就是answer。
完整代码
T1
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cout << "请输入魔卡数量：";
cin >> n;
int cards[101],sum=0;
cout << "请输入每张魔卡的价值：" << endl;
for (int i = 1; i <= n; ++i) {
cin >> cards[i];
sum += cards[i];
}
int dp[101][1001];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=cards[i];j<=sum/2;j++)
if(cards[i] <= j)
dp[i][j] = max(dp[i-1][j],dp[i-1][j-cards[i]] + cards[i]);
else
dp[i][j] = dp[i-1][j];
int ans = dp[n][sum/2];
cout<<ans<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=sum/2;j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
cout<<"ans = "<<sum-2*ans;
return 0;
}
|
输出结果
1
2
3
4
5
6
7
8
9
10
11
12
13
| 请输入魔卡数量：8
请输入每张魔卡的价值：
2 5 6 7 1 7 4 3
17
0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0 0 0 0 5 5 7 7 7 7 7 7 7 7 7 7 7
0 0 0 0 0 6 7 7 7 7 11 11 13 13 13 13 13
0 0 0 0 0 0 7 7 7 7 11 11 13 14 14 14 14
1 1 1 1 1 1 7 8 8 8 11 12 13 14 15 15 15
0 0 0 0 0 0 7 8 8 8 11 12 13 14 15 15 15
0 0 0 4 4 4 7 8 8 8 11 12 13 14 15 16 17
0 0 3 4 4 4 7 8 8 10 11 12 13 14 15 16 17
ans = 1
|
1
2
3
4
5
6
7
8
9
10
| 请输入每张魔卡的价值：
5 3 2 2 2 2
8
0 0 0 0 5 5 5 5
0 0 3 3 5 5 5 8
0 2 3 3 5 5 7 8
0 2 3 4 5 5 7 8
0 2 3 4 5 6 7 8
0 2 3 4 5 6 7 8
ans = 0
|
T2
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<bits/stdc++.h>
using namespace std;
int main(){
int n,k,prices[100],dp[101][101];
cin>>n>>k;
memset(dp,0,sizeof(dp));
memset(prices,0,sizeof(prices));
for(int i=1;i<=n;i++)
cin>>prices[i];
for(int i=1;i<=k;i++){
int maxDiff = -prices[1];
for(int j=1;j<=n;j++){
dp[i][j] = max(dp[i][j-1],prices[j] + maxDiff);
maxDiff = max(maxDiff, dp[i-1][j] - prices[j]);
}
}
cout<<dp[k][n]<<endl;
cout<<"|dp|";
for(int i=1;i<=n;i++)
cout<<i<<"|";
cout<<endl;
cout<<"|";
for(int i=1;i<=n+1;i++)
cout<<"-|";
cout<<endl;
for(int i=1;i<=k;i++){
cout<<"|"<<i<<"|";
for(int j=1;j<=n;j++)
cout<<dp[i][j]<<"|";
cout<<"\n";
}
return 0;
}
|
输出结果
1
2
3
4
5
6
7
| 6 2
3 2 7 5 1 4
8
|dp|1|2|3|4|5|6|
|-|-|-|-|-|-|-|
|1|0|0|5|5|5|5|
|2|0|0|5|5|5|8|
|
