knapsack-problem

1熱度

1回答

我已經用兩種算法（貪婪和動態規劃算法）編寫了分數揹包問題，我必須對它們進行比較..我只是在時間和空間複雜度方面做了比較..我不知道什麼其他因素可以用於兩種算法之間的比較.. 我希望任何人都可以幫助我，併爲我提供任何想法。

0熱度

1回答

我得到了一組數字。（最大爲110組數字）例如，我有3個數字中的陣列： 5.0 , 90.0, 8.5 我有另一號碼。在這個例子中可以說98.6。如何確定總和低於單個數字（98.6）的最大數字？在這個例子中，我們可以選擇低於98.6的90.0和8.5。

0熱度

1回答

改進的動態揹包 - 有問題的輸入？

以下是this SPOJ問題的嘗試解決方案。輸入是：值和使用貨幣的硬幣對應的權重和目標硬幣一定數額的金錢的總重量是找的錢一定量的最小可能的貨幣價值。我微微的揹包問題修改從wikipedia article揹包問題的動態規劃的解決方案 - 我只是第一個重量排序的硬幣，所以我沒有去通過所有的硬幣來獲得的最小值並且（希望）確保組合的重量等於容量。（請看代碼，它非常簡單並且評論。）但是，根據判斷

1熱度

1回答

固定數量的揹包0-1

我正在寫一個具有多個約束的揹包0-1的變體。除了權重約束之外，我還有一個數量約束，但是在這種情況下，我想解決揹包問題，因爲我需要在揹包中包含n件物品，重量小於或等於W.目前正在基於Rosetta Code的代碼http://rosettacode.org/wiki/Knapsack_problem/0-1#Ruby實施針對簡單0-1案例的動態編程ruby解決方案。實現固定數量限制的最佳方式是什麼

1熱度

1回答

派對時間表 - 古典揹包

輸入是一個可用的預算，派對數量，每個派對的門票價格和聚會上的樂趣。任務是通過可用的預算和使用的預算輸出儘可能多的樂趣。如果您可以選擇同樣樂趣的兩方，請選擇便宜的一方。（這是一個SPOJ problem。）我創建了兩個數組： m[i][j]從各方得到最大的樂趣多達我預算Ĵ p[i][j]最低價格PY來獲得最大的。從各方多達我與預算Ĵ樂趣然後，對每個I高達#parties和對每個j達到預算我

0熱度

2回答

Java中的遞歸揹包

我已經閱讀了很多揹包問題的變體，但我負責的版本有點不同，我不太明白如何解決它。我有一個代表權重的整數數組（即{1,4,6,12,7,2}），並且只需要找到一個合計目標權重的解決方案。我明白基本的算法，但我不明白如何實現它。首先，我的基本情況是什麼？數組是否爲空？目標已經達到？目標已經超過了？或者也許有一些組合？其次，當目標超出時，我該如何回溯並嘗試下一個項目？三，我應該返回什麼？我應該回

1熱度

2回答

Genymotion Android 4.4.2 Api 19不再啓動

我使用Genymotion與4.4.2 API19自定義手機7. Genymotion無法啓動。所以我從虛擬盒子啓動。在虛擬盒子上未跟蹤的pid系列之後，它啓動了android徽標，磁盤指示燈顯示一些活動，但沒有發生任何事情。我已經嘗試了一切從你的建議。我現在可以做什麼？任何想法都被接受！提前致謝！最好的問候保羅。

0熱度

1回答

如何在揹包中找到元素（扭曲 - 需要所有獲取元素的方法）

這是一個經典的揹包問題，我已經使用動態規劃方法解決了這個問題。從here開始，我創建了一個類似的方法來確定構成揹包的元素的類型。我需要找出最終答案可以得到的所有方式，而不僅僅是一種方式。我怎樣才能做到這一點？目前，我只能向後找到一種方法，將我的項目添加到最大值。但是在我的輸入中，我可能有兩種或兩種以上的方法來增加項目的最大值。我想知道這兩種或兩種以上的方式，因爲那時我必須根據一些標準選擇一組最

-2熱度

1回答

揹包變體。想法？

我有以下揹包問題的變體：我想買一個產品的X單位在最小的成本，並有m個農民，提供： - ，我可以選擇最多一個選項來自每個農民。形式上，我想能否請你讓我知道如果這個問題類似於0-1揹包問題的變種？如果你能提供任何參考資料，我可以找到關於這個或任何相關算法的更多信息，我將不勝感激。

0熱度

1回答

紅寶石 - 優化代碼從數組中尋找最佳選擇

我問了一個基本上是揹包問題的問題 - 我需要找到幾個不同數組的對象組合提供最佳輸出。例如，對於每個對象的「成本」限制，來自對象的最高「總和」值。我在這裏獲得的答案是以下各項 a.product(b,c) .select{ |arr| arr.reduce(0) { |sum,h| sum + h[:cost] } < 30 } .max_by{ |arr| arr.reduce(0) { |s