背包九讲Java版本

大家好，又见面了，我是你们的朋友全栈君。

package dp;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/** * 背包九讲 * * @ProjectName: algorithm * @Package: dp * @Description: TODO * @Author: bipa * @Date: 2022/1/8 8:00 */
public class Pack { 

/** * 01背包（每样物品的数量为一个） * * @param n 物品样数 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @return 总体积不超过m的最大价值 */
public static int pack01(int n, int m, int[] v, int[] w) { 

int[] dp = new int[m + 1];
for (int i = 0; i < n; i++) { 

for (int j = m; j >= v[i]; j--) { 

dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
return dp[m];
}
/** * 01背包方案数 * * @param n 物品数量 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @param mod 10^9 + 7 * @return 最优选法的方案数 */
public static int getNumber(int n, int m, int[] v, int[] w, int mod) { 

int[] dp = new int[m + 1], num = new int[m + 1];
Arrays.fill(dp, Integer.MIN_VALUE);
num[0] = 1;
dp[0] = 0;
for (int i = 0; i < n; i++) { 

for (int j = m; j >= v[i]; j--) { 

int temp = Math.max(dp[j], dp[j - v[i]] + w[i]);
int sum = 0;
if (temp == dp[j]) { 

sum += num[j];
}
if (temp == dp[j - v[i]] + w[i]) { 

sum += num[j - v[i]];
}
if (sum >= mod) { 

sum -= mod;
}
dp[j] = temp;
num[j] = sum;
}
}
int max = 0;
for (int i = 0; i <= m; i++) { 

max = Math.max(max, dp[i]);
}
int res = 0;
for (int i = 0; i <= m; i++) { 

if (max == dp[i]) { 

res += num[i];
if (res >= mod) { 

res -= mod;
}
}
}
return res;
}
/** * 01背包具体方案 * * @param n 物品数量 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @param link 连接符 * @return 最优选法的具体方案 */
public static String getPath(int n, int m, int[] v, int[] w, String link) { 

int[][] dp = new int[n + 1][m + 1];
for (int i = n - 1; i >= 0; i--) { 

for (int j = 0; j <= m; j++) { 

dp[i][j] = dp[i + 1][j];
if (j >= v[i]) { 

dp[i][j] = Math.max(dp[i][j], dp[i+1][j - v[i]] + w[i]);
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) { 

if (dp[i][m] == dp[i+1][m- v[i]] + w[i]) { 

sb.append(link).append(i);
m -= v[i];
}
}
return sb.substring(1);
}
/** * 完全背包（每样物品的数量无限制） * * @param n 物品样数 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @return 总体积不超过m的最大价值 */
public static int packComplete(int n, int m, int[] v, int[] w) { 

int[] dp = new int[m + 1];
for (int i = 0; i < n; i++) { 

for (int j = v[i]; j <= m; j++) { 

dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
return dp[m];
}
/** * 多重背包（每样物品的数量为s） * * @param n 物品样数 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @param s 每样物品的数量 * @return 总体积不超过m的最大价值 */
public static int packMultiple(int n, int m, int[] v, int[] w, int[] s) { 

int[] dp_I = new int[m + 1];
for (int i = 0; i < n; i++) { 

for (int j = m; j >= v[i]; j--) { 

for (int k = 1; k <= s[i] && k * v[i] <= j; k++) { 

dp_I[j] = Math.max(dp_I[j], dp_I[j - k * v[i]] + k * w[i]);
}
}
}
/** * 二进制优化，将每样物品的数量进行二进制拆分 */
int[] dp_II = new int[m + 1];
class Goods { 

int v; // 体积
int w; // 价值
Goods(int v, int w) { 

this.v = v;
this.w = w;
}
}
List<Goods> goods = new ArrayList<>();
for (int i = 0; i < n; i++) { 

int k = s[i];
for (int j = 1; j <= k; j *= 2) { 

k -= j;
goods.add(new Goods(j * v[i], j * w[i]));
}
if (k > 0) { 

goods.add(new Goods(k * v[i], k * w[i]));
}
}
for (Goods g : goods) { 

for (int i = m; i >= g.v; i--) { 

dp_II[i] = Math.max(dp_II[i], dp_II[i - g.v] + g.w);
}
}
return dp_I[m];
}
/** * 二维费用背包 * * @param n 物品样数 * @param V 背包体积 * @param M 背包承受重量 * @param v 物品体积 * @param m 物品质量 * @param w 物品价值 * @return 总体积不超过V，总质量不超过M的最大价值 */
public static int packTwo(int n, int V, int M, int[] v, int[] m, int[] w) { 

int[][] dp = new int[V + 1][M + 1];
for (int i = 0; i < n; i++) { 

for (int j = V; j >= v[i]; j--) { 

for (int k = M; k >= m[i]; k--) { 

dp[j][k] = Math.max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]);
}
}
}
return dp[V][M];
}
/** * 分组背包（每组物品最多选一个） * * @param n 组的数量 * @param m 背包容量 * @param v 物品体积 * @param w 物品价值 * @return 总体积不超过m的最大价值 */
public static int packGroup(int n, int m, List<Integer>[] v, List<Integer>[] w) { 

int[] dp = new int[m + 1];
for (int i = 0; i < n; i++) { 

for (int j = m; j >= 0; j--) { 

for (int k = 0; k < v[i].size(); k++) { 

if (j >= v[i].get(k)) { 

dp[j] = Math.max(dp[j], dp[j - v[i].get(k)] + w[i].get(k));
}
}
}
}
return dp[m];
}
}