做的网站名,wordpress安装首页怎么写,各个国家的google网站,免费的正能量视频素材网站问题描述 John 有两个孩子#xff0c;在 John病逝后#xff0c;留下了一组价值不一定相同的魔卡#xff0c; 现在要求你设计一种策略#xff0c;帮John的经管人将John的这些遗产分给他的两个孩子#xff0c;使得他们获得的遗产差异最小#xff08;每张魔卡不能分拆#…问题描述 John 有两个孩子在 John病逝后留下了一组价值不一定相同的魔卡 现在要求你设计一种策略帮John的经管人将John的这些遗产分给他的两个孩子使得他们获得的遗产差异最小每张魔卡不能分拆。 假设已知某股票连续若干天的股价并且如何时候你手上只能由一支股票即如果你要买入就得先将手上股票卖出设计一个算法来计算你所能获取的最大利润。你最多可以完成 k笔交易。也就是说你最多可以买k 次卖 k 次。 输入k 2, prices [3,2,7,5,1,4]
输出87-2 4-1解题思路
T1
这是一个经典的贪心算法问题
将所有的魔卡按照价值从大到小排序。从价值最高的魔卡开始依次分配给两个孩子中当前遗产较少的那个孩子。重复步骤2直到所有的魔卡都被分配完毕。 这种贪心分东西的思路非常常见一眼望穿 类似的题目还有捡大小垃圾放两个垃圾袋呀等等。
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]) maxDiffmax(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运算结果如下所示。
prices327514dp[1][j]005555dp[2][j]005558
这个dp[k][n]就是answer。
完整代码
T1
#include iostream
#include algorithmusing namespace std;// 分配遗产的函数
void distributeInheritance(int cards[], int n) {// 排序魔卡sort(cards, cards n, greaterint());// 初始化两个孩子的遗产值int child1_inheritance 0;int child2_inheritance 0;// 分配遗产for (int i 0; i n; i) {if (child1_inheritance child2_inheritance) {child1_inheritance cards[i];} else {child2_inheritance cards[i];}}// 输出两个孩子的遗产差异cout 遗产差异最小为 abs(child1_inheritance - child2_inheritance) endl;
}int main() {// 输入魔卡数量int n;cout 请输入魔卡数量;cin n;// 输入每张魔卡的价值int cards[n];cout 请输入每张魔卡的价值 endl;for (int i 0; i n; i) {cin cards[i];}// 调用分配遗产函数distributeInheritance(cards, n);return 0;
}/* sample input
8
2 5 6 7 1 7 4 3
*/输出结果
请输入魔卡数量8
请输入每张魔卡的价值
2 5 6 7 1 7 4 3
遗产差异最小为1T2
#includebits/stdc.h
using namespace std;
int main(){int n,k,prices[100],dp[101][101]; // 动态规划数组大小修改为dp[101][101]cinnk;memset(dp,0,sizeof(dp));memset(prices,0,sizeof(prices));for(int i1;in;i)cinprices[i];for(int i1;ik;i){int maxDiff -prices[1]; // 数组prices的下标从1开始for(int j1;jn;j){ dp[i][j] max(dp[i][j-1],prices[j] maxDiff);maxDiff max(maxDiff, dp[i-1][j] - prices[j]);}}coutdp[k][n]endl;// 打印dp数组cout|dp|;for(int i1;in;i)couti|;coutendl;cout|;for(int i1;in1;i)cout-|;coutendl;for(int i1;ik;i){cout|i|;for(int j1;jn;j)coutdp[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|
