問題描述
-
John 有兩個孩子，在 John病逝后，留下了一組價值不一定相同的魔卡， 現在要求你設計一種策略，幫John的經管人將John的這些遺產分給他的兩個孩子，使得他們獲得的遺產差異最小（每張魔卡不能分拆）。
-
假設已知某股票連續若干天的股價，并且如何時候你手上只能由一支股票，即如果你要買入就得先將手上股票賣出，設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k筆交易。也就是說，你最多可以買k 次，賣 k 次。
輸入：k = 2, prices = [3,2,7,5,1,4] 輸出：87-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就是代表本次買賣狀態下的累計成本(比較難理解)。所以 m a x D i f f = m a x ( m a x D i f f , d p [ i ? 1 ] [ j ] ? p r i c e s [ j ] ) maxDiff = max(maxDiff, dp[i-1][j] - prices[j]) maxDiff=max(maxDiff,dp[i?1][j]?prices[j])
對于每一天，都有去賺錢和不賺錢。不賺錢利潤等于昨天的利潤，去賺錢的利潤等于累計成本maxDiff加上prices[j]，因此 d p [ i ] [ j ] = m a x ( d p [ i ] [ j ? 1 ] , p r i c e s [ j ] + m a x D i f f ) dp[i][j] = max(dp[i][j-1], prices[j] + maxDiff) 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
#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 middle;
// if(sum % 2 ==0)
// middle = sum/2;
// else
// middle = sum/2 + 1;
// cout<<"middle = "<<middle<<endl;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;
}/* sample input
8
2 5 6 7 1 7 4 36
5 3 2 2 2 2
*/
輸出結果
請輸入魔卡數量：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
請輸入每張魔卡的價值：
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
#include<bits/stdc++.h>
using namespace std;
int main(){int n,k,prices[100],dp[101][101]; // 動態規劃數組大小修改為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]; // 數組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;// 打印dp數組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;
}/* simple input
6 2
3 2 7 5 1 4
*/
輸出結果
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|
)
