問題：有一個A物件的集合，A的長度為n，每個A有金額x，利息y的屬性，均為浮點型。現要從集合中選出若干A，要求總金額不超過k且利息最小，選出的A的個數為m，請問用java怎么解決？
我試著用回溯演算法來解決這個問題，目前碰到的問題是當n超過50時，計算耗時非常多，不知道是不是演算法有什么問題。
請問有沒有大佬分享下解決思路。
uj5u.com熱心網友回復：
問題更正一下，不是A的長度為n，應為集合的長度為nuj5u.com熱心網友回復：
你這問題很像0-1背包問題。現在記不太清了，不過我記得當初這個問題是用的動態規劃法解決的，并不是回溯法。運籌學里面有講，你可以去看看相關資料uj5u.com熱心網友回復：
考慮過用動態規劃，但是列不出狀態轉移方程。uj5u.com熱心網友回復：
頂頂頂頂頂頂uj5u.com熱心網友回復：
條件給錯了吧，選0個不就行了？uj5u.com熱心網友回復：
不好意思，條件確實少了一個，總金額不能小于xuj5u.com熱心網友回復：
經驗證，該問題不適合用動態規劃演算法實作，已用貪心演算法解決。uj5u.com熱心網友回復：
首先根據利息對集合進行排序，然后遍歷判斷金額即可轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/120133.html
標籤：Java相關
上一篇：求大老幫忙一下，怎么解決問題
下一篇：大哥們。約嗎？