动态规划分配礼物问题

发布网友发布时间：2022-05-09 17:44

共3个回答

热心网友时间：2023-10-11 02:34

思想：
1：对礼物的价值排序，采用快速排序，从价值大到小排序。
2：主体思想：
2.1初始化：把第一个礼物分给Alan，第二个礼物分给Bob，并以a、b纪录2者的个人的总价值
2.2：循环以下动作，直到分配结束：
if a<=b，把下一个礼物分给Alan
else ，把下一个礼物分给Bob

复杂度：排序复杂度为O( n*logn )，核心算法复杂度：O( n )，所以总体复杂度为O( n*logn )。
思想：没有按照你要求的动态规划的思想方法，而是采用了贪心算法，貌似要比动规简便。

热心网友时间：2023-10-11 02:35

用f(i,s)表示在Alan比Bob礼物价值多出s的情况下，来分1~i这个i个礼物，最终两人的差值绝对值最小，f(i,s)返回这个最小绝对值。则要求的问题为f(n，0），f(i,s)递推关系式为：
|s| i=0
f(i,s)={
min{f(i-1,s+vi) , f(i-1,s-vi)} i>0
写出上式的动态规划程序即可。

热心网友时间：2023-10-11 02:35

思想：
1：对礼物的价值排序，采用快速排序，从价值大到小排序。
2：主体思想：
2.1初始化：把第一个礼物分给Alan，
第二个礼物分给Bob，并以a、b纪录2者的个人的总价值
2.2：循环以下动作，直到分配结束：
if
a<=b，把下一个礼物分给Alan
else
，把下一个礼物分给Bob
复杂度：排序复杂度为O(
n*logn
)，核心算法复杂度：O(
n
)，所以总体复杂度为O(
n*logn
)。
思想：没有按照你要求的动态规划的思想方法，而是采用了贪心算法，貌似要比动规简便。