动态规划分配礼物问题

来源：百度知道 编辑：UC知道 时间：2024/06/28 07:29:27
两兄弟Alan和Bob，共同分配n个礼物。每个礼物只能分给其中的一人，且不能分成两个。每个礼物i∈{1,…，n}的价值为vi,为一正整数。设a和b分别表示Alan和Bob所收到礼物的总价值，V==a+b为使两兄弟高兴，我们希望尽可能地均分这些礼物，即使得|a-b|达到最小。
（1）试设计一O（n• V）时间的动态规划算法，使得|a-b|达到最小，并求出礼物集合{1，…，n}的相应分割。
请给出解这题的思想？？

思想：
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 )。
思想：没有按照你要求的动态规划的思想方法，而是采用了贪心算法，貌似要比动规简便。

用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
写出上式的动态规划程序即可。