子集和概率的變化。 （多個約束）

Question

讓我給你上，我試圖解決正常的子集和問題的變化的一個例子：

給出的一組小號 = {1,2,3， 4,5,6,7,8,9}具有最大容量C0 = 40。此外，我們有上的3項不同子集附加3個約束小號：

1. S1 = {2,3， 4}約束c1 = 5
2. S2 = {3 ，4,5,6}與約束C2 = 12
3. S3 = {7,8,9}與約束C3 = 25

的目標是找到的小號使得一個子集

• 路口是possib： - （C4 C0）

  重要的總和（所包括的項目），而不超出任何定約束最大化嘞！ （請參閱S1 & S2）

• 3只是約束計數的一個例子 - 它可能會更多！
• 雖然S的項目是整數值在這個例子中，它也可能是正實數

問： 這是否特定子集和問題有一個特定的名稱和/或有有沒有關於此的任何論文/文獻評論？

Answer 1

這聽起來像揹包問題：https://en.wikipedia.org/wiki/Knapsack_problem

見的子集和問題該文章中的部分：

「的子集和問題是決策的特殊情況和0-1的問題，其中每種類型的項目，權重等於值[...]在密碼學領域，術語揹包問題通常用於具體指代子集和問題，並且通常被稱爲卡爾普21個NP完全問題之一。 [30]

子集求和問題的推廣被稱爲多子集求和概率lem，其中多個分箱以相同的容量存在。 [31]「