0-1背包问题
/**
* 0-1背包问题
* 将n个价值为v,重量为v的物品放入限重为W的背包中,要求背包中物品的价值最高。
*
*/
import java.util.HashSet;
import java.util.Set;
public class Knapsack {
//物品的价值,为使数组下标从1开始,在index 0 的位置填充-1.
private static int[] v = { -1, 505, 352, 458, 220, 354, 414, 498, 545, 473, 543 };
//物品的重量,为使数组下标从1开始,在index 0 的位置填充-1.
private static int[] w = { -1, 23, 26, 20, 18, 32, 27, 29, 26, 30, 27 };
//物品个数
private static int n = 10;
//限重
private static int W = 67;
//最终选用物品的集合
private static Set<Integer> set = new HashSet<>();
//数组m[i][w],表示对于前i个物品,在限重是w的情况下,的重大价值。
//为使数组下标从1开始,+1.
private static int[][] m = new int[n + 1][W + 1];
public static void main(String[] args) {
//选取前0件物品时的情况
for (int j = 0; j <= W; j++) {
m[0][j] = 0;
}
//限重为0时的情况
for (int i = 1; i <= n; i++) {
m[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
//第i件物品的重量大于背包的承重,该物品不能被放入。
//这时,m[i][j]等于放置前i-1个物品,限重为j时的最优解,既m[i-1][j].
if (w[i] > j) {
m[i][j] = m[i - 1][j];
//否则,该第i件物品有可能被放入背包中。具体情况为:
} else {
//假如没放物品i:
m[i][j] = Math.max(m[i - 1][j],
//假设放入了物品i:
m[i - 1][j - w[i]] + v[i]);
}
}
}
knapsack(n, W);
System.out.println(set.toString());
}
public static Set<Integer> knapsack(int i, int j) {
if (i == 0)
return new HashSet<Integer>();
if (m[i][j] > m[i - 1][j]) {
set.add(i);
//集合的交
set.addAll(knapsack(i - 1, j - w[i]));
return set;
} else
return knapsack(i - 1, j);
}
}
标签:背包,int,private,问题,set,static,物品
From: https://www.cnblogs.com/funflux/p/17473335.html