01背包穷举法java

01背包问题是一个经典的动态规划问题，其目标是在给定的一组物品中选择一些物品放入一个容量为W的背包中，使得背包中物品的总价值最大。穷举法是其中一种解决方法，其思路是利用递归进行遍历求出各个的可能性，将遍历出的结果存入数组中，进行缓存。然后遍历缓存数组，将符合题目要求的背包情况存入到Map中，最后遍历出Map中最大的价值对应的背包情况即可。下面是Java代码实现：

public class Knapsack {
private static int[] weight = {12, 2, 1, 1, 4}; // 物品重量
private static int[] value = {14, 2, 1, 1, 10}; // 物品价值
private static int N = 5; // 物品数量
private static int W = 15; // 背包容量
private static int[] back = new int[N]; // 缓存数组
private static Map<String, Integer> map = new HashMap<>(); // 存储背包情况和对应的价值

public static void main(String[] args) {
knapsack(0);
int maxValue = 0;
String maxKey = "";
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() > maxValue) {
maxValue = entry.getValue();
maxKey = entry.getKey();
}
}
System.out.println("最大价值为：" + maxValue);
System.out.println("背包情况为：" + maxKey);
}

private static void knapsack(int n) {
if (n >= N) {
int totalWeight = 0;
int totalValue = 0;
for (int i = 0; i < N; i++) {
if (back[i] == 1) {
totalWeight += weight[i];
totalValue += value[i];
}
}
if (totalWeight <= W) {
String key = Arrays.toString(back);
map.put(key, totalValue);
}
return;
}
back[n] = 0;
knapsack(n + 1);
back[n] = 1;
knapsack(n + 1);
}
}