介紹
給定 n 種物品和一個容量為 C 的背包，物品 i 的重量是 ，其價值為
問：應該如何選擇裝入背包的物品，使得裝入背包中的物品的總價值最大？
背包問題是具有許多應用的組合優(yōu)化問題
背包問題
在背包問題中，我們有一組物品。每個物品都有重量和價值：
背包算法示例.png
我們想將這些物品放入背包。但是，它有一個重量限制：
書包最大重量
因此，我們需要選擇總重量不超過重量限制的物品，并且其總價值達到最高。 例如，上述示例的最佳解決方案是選擇5kg和6kg物品，它們在重量限制內的最大值為40元。
背包問題有幾種變化，我們將重點介紹0-1背包問題。在0-1背包問題中，必須選擇每個物品或將其留在后面。我們不能取一部分物品。另外，我們不能多次取一件物品。
數(shù)學公式
現(xiàn)在讓我們以數(shù)學符號形式化0-1背包問題。給定一組n個物品和重量限制W，我們可以將優(yōu)化問題定義為：
數(shù)學公式
這個問題是NP完全難題。因此，目前尚無多項式時間算法可以解決。但是，對于此問題，可以使用動態(tài)規(guī)劃算法思路來解決。
遞歸算法
使用遞歸公式來解決此問題：
遞歸算法
在該公式中，
重量限制為w的（n-1）個物品的最優(yōu)解（不包括第n個項目）
第n個物品的值加上（n-1）個物品的最優(yōu)解和w減去第n個物品的權重（包括第n個物品）
如果第n項的重量大于當前的重量限制，則不包括在內。因此，它屬于上述兩種情況的第一類。
JAVA中實現(xiàn)此遞歸公式代碼：
遞歸算法實現(xiàn)-Java
.
在每個遞歸步驟中，我們需要評估兩次最優(yōu)解決邏輯，因此，此遞歸解決方案的運行時間為O（2的n次方）。
動態(tài)規(guī)劃算法
動態(tài)規(guī)劃思路是一種用于線性化，指數(shù)級遞增的編程算法的思路，這個思路是存儲子問題的結果，這樣我們以后就不必重新計算它們了。
我們還可以通過動態(tài)規(guī)劃解決0-1背包問題。要使用動態(tài)規(guī)劃中，我們使用自下而上的方法來計算最佳解決方案：
/**
* @param w : 已知物品重量數(shù)組集合
* @param v : 已知物品價值數(shù)組集合
* @param n ： 最大價值，0 表示不要求
* @param W : 最大重量，0 表示不要求
* @author 油膩的Java
* @date 2019/11/5
* @return
*/
public int knapsackDP(int[] w, int[] v, int n, int W) {
if (n <= 0 || W <= 0) {
return 0;
}
/**
* 創(chuàng)建臨時數(shù)組
*/
int[][] m = new int[n + 1][W + 1];
for (int j = 0; j <= W; j++) {
m[0][j] = 0;
}
/**
* 遍歷n和W,
*/
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (w[i - 1] > j) {
//對m數(shù)組進行賦值
m[i][j] = m[i - 1][j];
} else {
//求最大值
m[i][j] = Math.max(m[i - 1][j], m[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
return m[n][W];
}
在代碼中，我們在商品價值n和重量限制W上有一個嵌套循環(huán)。因此，它的運行時間為O（nW）。
單元測試
最后針對各自的場景做了一下單元測試
同時滿足價格，重量最大化
最大重量最優(yōu)解
最大價格最優(yōu)解
結論
本文通過編寫遞歸算法、動態(tài)規(guī)劃算法來解決背包0-1問題，以及測試相應的單元測試，希望在背包算法對你有新的認知。
