舊和著名揹包問題需要給定的容量C和的n項{I_1，I_2，...，1-N}與每個I_j =（weight_j，value_j）的列表，一個試圖在填滿揹包的同時最大化價值。最大化揹包與附加約束
但是，如果我們添加約束條件會發生什麼
1）特定項目選擇必須是0或者必須是奇數（例如次數：只能採取既沒有10磅啞鈴或1 ，3，5，..他們的數量）。對於所有j，2 = C = n^2和n = < = weight_j < = n^2。
什麼樣的動態編程實現可以用來處理額外的約束？
一些建議將非常感謝如何開始。謝謝！
可以制定揹包問題這變化作爲整數規劃
標準揹包問題：
Maximize sum(j) Value_j x X_j
subject to
sum(j) Wt_j x X_j <= C
X_j is integer
在您的變體中，X_j只能採用不同的值：{0，1,3,5，...}
制定約束以限制X取奇數值
每當有變量可以採用這些類型的值限制時，就引入0/1變量來處理這些條件。
對於每個項目j我們來介紹一些二進制變量和以及一些新的約束。
X_j - 1 Y_j1 - 3 Y_j3 - 5 Y_j5 ... - M Y_jm = 0
m是Xj可以採用的最大值（奇數）。
，並限制X_j承擔這些值中的一個，我們添加
Y_j0 + Y_j1 + Y_j3 + ... + Y_jm = 1 for each item j
Y_j0, Y_j1, Y_j3 ..., Y_jm are {0,1} (binary)
變量Y_j0是讓X_j採取值0
事實上，C = n^2，確保我們能夠爲每個約束提出合理的上限m。
您現在可以用整數規劃求解器來求解這個修改後的揹包。它仍然會按照「數值密度」（每千克數值）的降序查找物品，而限制爲奇數值的約束條件會在某些邊界條件下生效。
希望有所幫助。
揹包問題是一個整數規劃問題，最簡單的形式可以通過動態規劃解決。即使看起來很小的變化也會使問題變得更加困難，更適合其他方法。最直截了當的方法是將它放鬆到一些線性程序，同時使用分支並通過可行的解決方案來解決問題。也可以使用切割平面 - 但人們通常會發現它更易於理解和實施分支和邊界。看看這裏http://mat.gsia.cmu.edu/orclass/integer/integer.html（更簡單，更方便）http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf（更完整）
是不是隻是「消除」一些細胞的DP問題？ – user2246674