共計 582 個字符，預計需要花費 2 分鐘才能閱讀完成。

背包問題是一個經典的動態規劃問題，有多種解決方法。下面是一種常見的解決方案：

1. 定義一個 2 維數組 dp，其中 dpi 表示在前 i 個物品中，背包容量為 j 時能夠裝入的最大價值。
2. 初始化 dp 數組，將第一行和第一列都置為 0，表示背包容量為 0 時和沒有物品可選時，都無法裝入任何物品。
3. 使用雙層循環遍歷所有物品和背包容量：

• 如果當前物品的重量大于背包容量，則無法裝入，dpi = dpi-1；
• 否則，可以選擇裝入該物品或不裝入該物品，取較大的價值：
• 如果選擇裝入該物品，dpi = dpi-1] + v[i]，其中 w[i] 表示第 i 個物品的重量，v[i] 表示第 i 個物品的價值；
• 如果選擇不裝入該物品，dpi = dpi-1。

1. 最后返回 dpn，其中 n 表示物品的個數，W 表示背包的容量。

下面是一個示例代碼：

public int knapSack(int W, int[] w, int[] v, int n) {int[][] dp = new int[n+1][W+1];
for (int i = 0; i <= n; i++) {for (int j = 0; j  j) {dp[i][j] = dp[i-1][j];
} else {dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
}
}
}
return dp[n][W];
}

這個解決方案的時間復雜度為 O(nW)，其中 n 為物品個數，W 為背包容量。

丸趣 TV 網 – 提供最優質的資源集合！