1背包問題 ```java package net.zhaoxuyang.common.algorithm.dp; import java.util.Arrays; /** * 0-1 背包問題 * * <pre> * n個物品和1個背包，對物品i，價值為v[i]，重量為w[i]，背包容量為W，如何裝入使得總價值最大: * - w[i]x[i]小于等于W * - x[i]∈{0,1} * - 目標函數為max(v[i]x[i]) * - 其中i∈[1,n] * * 假如(x[1], x[2], x[3], ..., x[n])是最優解， * 那么(x[2], x[3], ..., x[n])則是以下問題的一個最優解： * - w[i]x[i] 小于等于 W - w[1]x[1] * - x[i]∈{0,1} * - 目標函數為max(v[i]x[i]) * - 其中i∈[2,n] * * </pre> * * 時間復雜度為O(nW) * 缺點：要求w數組中的元素為整數；當W>2^n時，時間復雜度為O(n2^n) * @author zhaoxuyang */ public class KnapSack { public static void main(String[] args) { int[] w = {2, 2, 6, 5, 4}; int[] v = {6, 3, 5, 4, 6}; int W = 10; byte[] result = fun(w, v, W); System.out.println(Arrays.toString(result)); } /** * * <pre> * 數組c[w.length+1][W+1]存放每次迭代的執行結果 * 數組x[w.length]存放所裝入的背包的物品狀態 * @初始化 c[0][j] = c[i][0] = 0 * * @遞歸式 c[i][j] = c[i-1][j] j 小于 w[i] * = max{c[i-1][j],c[i-1][j-w[i]]+v[i]} j大于等于w[i] * </pre> * @param w 重量 * @param v 價值 * @param W 容量 * @return 最優解 */ private static byte[] fun(int[] w, int[] v, int W) { int row = w.length; int col = W; byte[] x = new byte[row]; int[][] c = new int[row + 1][col + 1]; //存放各個子問題的最優值 for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { if (j < w[i - 1]) { c[i][j] = c[i - 1][j]; } else { int tmp = c[i - 1][j - w[i - 1]] + v[i - 1]; c[i][j] = Math.max(c[i - 1][j], tmp); } } } //構造最優解 for (int i = row, j = col; i > 0; i--) { if (c[i][j] > c[i - 1][j]) { x[i - 1] = 1; j -= w[i - 1]; } } return x; } } ```