找到子集給定條件的最大可能大小

Question

這是過去比賽中的一個問題。不幸的是，比賽沒有社論，所以我問這個問題。你可以驗證比賽結束：Problem Description

我試圖解決它使用DP使用子集和問題的變化。但我不知道如何執行比賽開始時現有燃油應超過比賽要求的條件。我正在計算差異並查看是否有可能少於使用子集總和的初始燃料的總和。但在這種情況下，我無法執行該約束。

任何人都可以幫我制定一個動態規劃算法的問題。或者，如果使用動態編程是不可能的，我可以使用什麼其他方法。

Answer 1

如果比賽的順序是固定的，那麼也許找到一個足夠快的動態程序會更容易。我將概述一個結構定理，即一種添加至少留下一個最優解的約束的方法。 DP可以利用這些限制，在這種情況下，這相當於比賽排序。這是改善動態程序運行時間的一般策略。

考慮一個特定的賽車時間表。假設錢德勒參加了比賽前的淨燃料消耗，淨燃料收益。沒有任何理由說他不能在賠率上贏得比賽：他在比賽開始時比他在可行的賽程中獲得更多的燃油。因此，我們可以假設錢德勒在所有損失之前安排所有收益。

假設錢德勒參加了前提燃料量s和s'的背靠背比賽。如果s> s'，那麼他可以再次開關，併爲兩場比賽找到更多的起跑燃料。我們可以認爲，收益是通過增加先決條件燃料來排序的。

假設錢德勒參加背靠背虧損比賽時需要燃油和s'。如果s < s'，那麼，你知道演習。我們可以假設損失是通過減少先決條件燃料來排序的。稍微打平一球，這就結束了我們的比賽總順序。