拿出11條數據//條件每個位置(position)的人數限制每隊(team)人數不能超過7人credits的總和在100分之內（包含100）總分(points)最高//位置人數限制position-1 : 1 position-2 : 3-5 position-3 : 1-3 position-4 : 3-5//模擬數據{points credits position team56 9.0 1 t154 9.1 2 t135 8.0 2 t232 8.0 3 t120 8.5 1 t218 9.0 3 t216 9.1 2 t215 8.0 3 t213 7.0 3 t110 8.5 4 t27 9.0 4 t25 8.0 2 t14 7.0 3 t13 8.5 4 t12 9.0 3 t11 8.5 4 t20 9.0 3 t20 8.5 4 t10 9.0 3 t20 8.5 4 t10 9.0 3 t10 8.5 4 t2... ... ... ...}
1 回答
泛舟湖上清波郎朗
TA貢獻1818條經驗 獲得超3個贊
這個和背包問題有點類似啊，首先包容量是 100，即credits <= 100。其次拿到的所有數據的Sum(points)最大。光這兩點就和背包問題非常相似。
背包問題是這樣描述的：
有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
背包問題求解使用了貪心算法，其中貪心策略是：每次選取單位重量價值最大的物品。
你這里類比一下，貪心策略是：每次選取單位credits?points最大的記錄，即points / credits最大的記錄。
在選取過程中需要注意一些條件：
一條記錄只能被選擇一次
相同的
Team選擇的次數小于等于7每個
position的限制選舉的條數達到11，或
credits達到100，則停止如果
credits先達到100，則考慮一種置換策略。
補充：
貌似貪心好像不行，換種思路，用回溯的方法去考慮：
首先，對所有記錄按照points倒序排序，構建一個搜索空間樹，樹高為11。所以原問題就變成了搜索樹的最佳路徑的問題。每次選取points最大的記錄，向下搜索時，可以根據條件過濾掉沒有必要的分支。每一步搜索時必須滿足一下條件：
相同記錄不能被搜索兩次。
相同的
Team選擇的次數小于等于7。每個
position的限制。對已選取的記錄
Sum(points) <= 100。
一旦搜索路徑上不滿足上述條件，則回溯，到另一個分支繼續搜索。所以整個是一個遞歸的過程。
補充：
用幾個測試用例簡單的測試了下，都是正確的，效率不是很高，你自己優化一下，下面是我的輸出：
輸入數據:
1???56??9.0??1???1??2???54??9.1??2???1??3???35??8.0??2???2??4???32??8.0??3???1??5???20??8.5??1???2??6???18??9.0??3???2??7???16??9.1??2???2??8???15??8.0??3???2??9???13??7.0??3???1??10??10??8.5??4???2??11??7???9.0??4???2??12??5???8.0??2???1??13??4???7.0??3???1??14??3???8.5??4???1??15??2???9.0??3???1??16??1???8.5??4???2??17??0???9.0??3???2??18??0???8.5??4???1??19??0???9.0??3???2??20??0???8.5??4???1??21??0???9.0??3???1??22??0???8.5??4???2??選取的數據：
1???56??9.0??1???1??2???54??9.1??2???1??3???35??8.0??2???2??4???32??8.0??3???1??6???18??9.0??3???2??7???16??9.1??2???2??8???15??8.0??3???2??10??10??8.5??4???2??11??7???9.0??4???2??12??5???8.0??2???1??14??3???8.5??4???1??sumPoints:251,?sumCredits:94.20,
?position-1?picked(1):?1?,?position-2?picked(3-5):?4?,?position-3?picked(1-3):?3?,?position-4?picked(3-5):?3??
?team?picked(less?than?7):{1=5,?2=6}添加回答
舉報
0/150
提交
取消