在this问题中，我们必须找到所需的单程票和家庭票的数量，以便价格最低如果价格是相同的许多安排，然后打印安排与最低票。
问题陈述
Acmestan的电影院有两种类型的票：一张票只适合一个人，而一张家庭票允许父母和他们的孩子进入电影院。不用说，一张家庭票的价格总是高于一张单程票，有时甚至高达单程票价格的五倍。
对于家庭来说，决定购买哪一种机票安排最经济是一件很有挑战性的事情。例如，右边图中所示的家庭有四张票可供选择：七张单人票；两张家庭票；一张家庭票（亚当、鲍勃、辛迪的）加上四张单人票；或者，一张家庭票（鲍勃和他的四个孩子的）加上其余两张单人票。
写一个程序来决定哪种票的价格最低如果有多个这样的安排，请打印票数最少的安排。
我的DP方法如下：
做家谱。
每个节点都应该有Min_Tickets（即最小票数）和Min_Price（即最小价格）字段。这些字段表示带那个人和他的孩子出去所需的最低金额此外，还有表示过程中涉及的家庭票（fam_tickets）和单张票（sin_tickets）数量的字段。
从叶节点开始初始化min_tickets=1和min_price= S（即单程票价格），fam_tickets=0，sin_tickets= 1。
现在对于其他节点考虑他的子孙后代。F是家庭票的价格。对于他们：
最小价格=最小（F+所有孙子孙女的最小价格总和，S+
所有儿童的最低价格合计）
如果孙子是空的，我们取min_price=0 and min_tickets=0
为了找出民宿票，我们从给出最低价格的信息中得出。如果两个阵型的价格相同，我们会：
if(1+ min_tickets of all grandchildren summed > 1+ min_tickets of all children summed)
min_tickets = 1+ min_tickets of all children summed;
fam_tickets= fam_tickets of all children summed;
sin_tickets= 1+ sin_tickets of all children summed;
else
min_tickets = 1+ min_tickets of all grandchildren summed;
fam_tickets= 1+ fam_tickets of all grandchildren summed;
sin_tickets= sin_tickets of all grandchildren summed;
这个解决方案正确吗提前谢谢。
最佳答案
在你的例子中，你是否考虑过购买两张家庭门票以获得最大利润的情况？
在你的解决方案中，当处理亚当的节点时，
min_price= min(F + min_price of all grandchildren summed , S + min_price of all children summed)
不会起作用的。
我不知道您实现的细节，但这是一个棘手的部分。希望它有帮助。:)
关于algorithm - SPOJ ANARC07G放手看电影吧，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20796507/