以下是什麼？

Question

我有一個簡單的算法問題。

• 我有一組正整數S和一個正整數i。
• 假設的S之和（或S一個子集）是其元素的總和。
• 我需要找到一個子集的Ss其總和不超過i，並「最大限度地總結」 - 意思的S沒有其它亞比s不超過i更大的總和。

，我想出了是走在各組發電機組的S的，總結的整數，保持鑲有我所尋求的性質的軌道，但這個算法顯然是指數平凡解。

必須有一個著名的名字對於這個問題，因爲我不認爲我是第一次遇到這種需要。有人可以幫我嗎？

Answer 1

解決子集和問題，使用動態規劃你的設置。

然後掃描填充表從第i個條目，以更小的值，直到找到非零項（即例如總和存在）。這是不超過給定值的最大總和。