在這個問題中，我們有具有不同價值的物品，但所有物品的重量都無關緊要。我們有一個利潤目標，我們希望通過選擇這些專案來實作。但是我們想要最少的專案并且專案是無限的。
所以假設我們的目標是 10，我們有值為 1、2、3、4 的專案。我們想要 4,4,2 而不是 3,3,3,1。它們具有相同的總價值，但我們想要的是具有相同利潤的最少數量的物品。
我已經推匯出動態和遞回方法來解決它，但對我來說的麻煩是我無法為我的遞回方法推匯出數學公式。
這是我的遞回方法
static int recursiveSolution(int[] values, int goal, int totalAmount) {
if (goal == 0)
return totalAmount;
if (goal < 0)
return Integer.MAX_VALUE;
totalAmount ;
int minAmount = Integer.MAX_VALUE;
for (int i = 0; i < values.length; i ) {
minAmount = Math.min(minAmount, recursiveSolution(values, goal - values[i], totalAmount));
}
return minAmount;
}
uj5u.com熱心網友回復：
假設您要求的是演算法的 Big-O...
這看起來像一個簡單的暴力求和搜索。不幸的是，這些的運行時間不容易估計，并且取決于輸入值及其計數 (N)。我所看到的此類解決方案的 Big-O 估計是這樣的：
Let
N = the number of values in the `values[]` array,
Gv = PRODUCT(values[])^(1/N)
(the geometric mean of the `values[]` array),
M = the target summation (`totalAmount`),
Then the complexity of the algorithm is (very approximately)
O(N^(M/Gv))
如果我沒記錯的話。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/403063.html
標籤：
上一篇：需要幫助理解x86程式集中的遞回