- 所有解:结合增量蛮力法 求解幂集的方法,先求出所有物品的组合
- 可行解:遍历所有的物品求物品和体积<=背包容量的物品组合
- 最优解:找出体积和最大的物品组合
package xcrj.kchalgorithm.bruteForce;
import java.util.*;
public class Knapsack01 {
static class Goods {
private int weight;
private int value;
public Goods() {
}
public Goods(int weight, int value) {
this.weight = weight;
this.value = value;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
public static Set> feasibleResults(Set> allResult, int availableWeight, int[] weights, int[] values) {
Set> feasibleWeightResult = new HashSet<>(8);
Set optimalValueResult = null;
int optimalValue = 0;
for (Set set : allResult) {
int weightSum = 0;
for (Integer code : set) {
weightSum += weights[code - 1];
}
// 可以放进背包的物品
if (weightSum <= availableWeight) {
Set feasibleSet = new HashSet<>(4);
for (Integer code : set) {
feasibleSet.add(code);
}
feasibleWeightResult.add(feasibleSet);
// 可以放进背包的物品价值
int sumValue = 0;
for (Integer code : set) {
sumValue += values[code - 1];
}
// 最大价值
if (sumValue > optimalValue) {
optimalValue = sumValue;
optimalValueResult = new HashSet<>(4);
for (Integer code : set) {
optimalValueResult.add(code);
}
}
}
}
System.out.println("所有可行解:");
System.out.println(feasibleWeightResult);
System.out.println("最优解:");
System.out.println(optimalValueResult);
return feasibleWeightResult;
}
public static Set> allResults(int n) {
Set> setSet = new HashSet<>(8);
// {} 空集
Set setNull = new HashSet<>();
setSet.add(setNull);
for (int j = 0; j < n; j++) {
Set> setSet2 = new HashSet<>(8);
// 保存原来的集合
for (Set set : setSet) {
Set set2 = new HashSet<>();
for (Integer v : set) {
set2.add(v);
}
setSet2.add(set2);
}
// 给原集合中的每个幂集增加j
for (Set set : setSet) {
set.add(j + 1);
}
// 将set2中的幂集放到set中,组合成新的集合
for (Set set : setSet2) {
setSet.add(set);
}
}
return setSet;
}
public static void main(String[] args) {
// 4个物品,能承受6公斤重量的背包
// 数组下标+1是物品的唯一编号
int[] weights = {5, 3, 2, 1};
int[] valuess = {4, 4, 3, 1};
Set> allResult = allResults(4);
feasibleResults(allResult, 6, weights, valuess);
}
}