0-1 背包问题
问题：给大小为n的数组weights[]和values[], 求在不超过W的情况下能取得的value总和最大是多少，每一个数只能最多取一次（或者不取）
本质是排列组合，复杂度O(2^n)
public static void main(String[] ss) {
int[] a = {1,2,3};
int[] b = {4,2,1};
int w = 3;
System.out.println(knap(a, b, w));
}
private static int maxValue = 0;
private static int knap(int weights[], int values[], int maxW) {
dfs(weights, values, 0, 0, 0, maxW);
return maxValue;
}
private static void dfs(int[] weights, int[] values, int curV, int curW, int index, int maxWeight) {
if (curW > maxWeight) {
return;
}
maxValue = Math.max(maxValue, curV);
for (int i = index; i < weights.length; i++) {
dfs(weights, values, curV + values[i], curW + weights[i], i + 1, maxWeight);
}
}
另一种写法。这种写法更容易看出我们可以用[index, curW] = weight来标记每一个状态（递归树上的结点）
O(2^n)
private static int knap(int weights[], int values[], int maxW) {
return dfs(weights, values, 0, 0, maxW);
}
private static int dfs(int[] weights, int[] values, int curW, int index, int maxWeight) {
if (index == weights.length) {
return 0;
}
int max_1 = 0;
if (curW + weights[index] <= maxWeight) {
max_1 = dfs(weights, values, curW + weights[index], index + 1, maxWeight) + values[index];
}
int max_2 = dfs(weights, values, curW, index + 1, maxWeight);
return Math.max(max_1, max_2);
}
Memoization
O(maxW * n)
private static int knap(int weights[], int values[], int maxW) {
int n = weights.length;
int[][] dp = new int[n][maxW + 1];
return dfs(weights, values, 0, 0, maxW, dp);
}
private static int dfs(int[] weights, int[] values, int curW, int index, int maxWeight, int[][] dp) {
if (index == weights.length) {
return 0;
}
if (dp[index][curW] != 0) {
return dp[index][curW];
}
int max_1 = 0;
if (curW + weights[index] <= maxWeight) {
max_1 = dfs(weights, values, curW + weights[index], index + 1, maxWeight, dp) + values[index];
}
int max_2 = dfs(weights, values, curW, index + 1, maxWeight, dp);
int rt = Math.max(max_1, max_2);
dp[index][curW] = rt;
return rt;
}
iterative dp, 通项公式跟递归是一摸一样
O(maxW * n)
private static int knap(int weights[], int values[], int maxW) {
int n = weights.length;
int[][] dp = new int[n][maxW + 1];
for (int i = 0; i < maxW + 1; i++) {
if (weights[0] <= i) {
dp[0][i] = values[0];
}
}
for (int i = 1; i < n; i ++) {
for (int j = 1; j < maxW + 1; j++) {
if (j - weights[i] >= 0) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
}else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n - 1][maxW];
}
可以发现当前的dp[row]只依赖于之前一行dp[row - 1], 所以可以简化为一维dp
private static int knap(int weights[], int values[], int maxW) {
int n = weights.length;
int[] dp1 = new int[maxW + 1];
int[] dp2 = new int[maxW + 1];
for (int i = 0; i < maxW + 1; i++) {
if (weights[0] <= i) {
dp1[i] = values[0];
}
}
for (int i = 1; i < n; i ++) {
for (int j = 1; j < maxW + 1; j++) {
if (j - weights[i] >= 0) {
dp2[j] = Math.max(dp1[j], dp1[j - weights[i]] + values[i]);
}else {
dp2[j] = dp1[j];
}
}
int[] tmp = dp1;
dp1 = dp2;
dp2 = tmp;
Arrays.fill(dp2, 0);
}
return dp1[maxW];
}
Unbounded knapsack
如果按0-1的解法的话会形成3个嵌套的for循环
换一种思路
![{\displaystyle m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{i}+m[w-w_{i}])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e429f861d2e4c29d3d03b350e51d5c1280d1c83)
, 
,
O(n * maxW)
private static int knap(int weights[], int values[], int maxW) {
int n = weights.length;
int[] dp = new int[maxW + 1];
for (int i = 1; i < maxW + 1; i++) {
for (int j = 0; j < n; j++) {
if (i >= weights[j]) {
dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
}
}
}
return dp[maxW];
}
ToDo
可以用贪心算法吗？v / w 最大的那个一直加
Bounded knapsack
