Objective-C的尋找算法

在我的應用程序需要確定哪些板塊，用戶可以在他們的槓鈴負荷達到理想的減肥。Objective-C的尋找算法

例如，用戶可以指定他們使用的是棒45鎊和具有45,35,25,10,5,2.5磅板使用。對於像115這樣的重量來說，這是一個很容易解決的問題，因爲結果與普通鋼板完美匹配。 115 - 45/2 = 35.

所以這裏的目標是找到用戶需要達到的重量的最大到最小的板（從選擇）。

我的起動方法看起來像這樣...

-(void)imperialNonOlympic:(float)barbellWeight workingWeight:(float)workingWeight { 
    float realWeight = (workingWeight - barbellWeight); 
    float perSide = realWeight/2; 

    .... // lots of inefficient mod and division .... 
}

我的思維過程是先確定每一側的重量會是什麼。總重量 - 槓鈴的重量/ 2。然後確定需要的最大到最小的板的數量（和每個的數量，例如325將是45 * 3 + 5或45,45,45,5。

與fmodf和一對夫婦的它發生，我認爲有可能是解決這個問題的算法。我一直在尋找到BFS，並承認這是我的頭頂，但仍願意給它一個鏡頭，其他的想法瞎搞。

欣賞到哪裏的算法或代碼示例看任何提示。

來源

2014-01-25 Jeremy

你不需要一個算法，因爲你已經有一個。做起來很容易，只是以最大的重量去比賽，直到剩下的比例低於這個數字，然後繼續下去並以5分的重量結束。 –

@JamesBlack它不會工作。它是一個分幣問題（使用DP解決）。你不能按照你所說的程序，例如，假設所需的總重量= 123，並且存在的重量是50,41,1。根據您的解決方案，您將擁有123 = 50 * 2 + 23 * 1（共25項），但123 = 41 * 3是最佳解決方案。您必須使用動態編程來獲取它。 http://stackoverflow.com/questions/4247662/the-minimum-number-of-coins-the-sum-of-which-is-s – santhu

Thanek，santhu。這很好地描述了問題，你的鏈接給了我一些東西來開始解決它。 – Jeremy

您的問題稱爲Knapsack problem，你會發現這個問題有很多解決方案。有此問題的一些變種。它基本上是一個動態臨編程（DP）問題。

一個常見的做法是，你開始服用的最大重量（但不到你想要的體重），然後取最大的剩餘重量。這很容易。我加入了一些更多的鏈接（Link 1，Link 2，Link 3），使得它變得清晰。但是有些問題可能難以理解，請跳過它們並嘗試着重於基本的揹包問題。祝你好運.. :)

讓我知道是否有幫助.. :)

來源

2014-01-25 06:48:15 Rashad

非常有幫助，真的很感激它。 – Jeremy

謝謝。你的問題讓我想起了過去的日子。一旦我花了很多時間解決ACM ICPC的算法問題。現在是一個全職開發人員..：P 真正的樂趣是解決問題.. :) – Rashad

Objective-C的尋找算法

回答

相關問題