01背包问题（注意看注释）
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。每种物品仅有一件，可以选择放或不放。求解将哪些物品装入背包可使价值总和最大。
f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程是
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v];如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。优化空间复杂度
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]} //这里的f[v]相当于f[i-1][v],f[v-c[i]]相当于f[i-1][v-c[i]-
进一步优化
for i=1..N
for v=V..0 //其实v不必循环到0 v=V..(V-c[i])
f[v]=max{f[v],f[v-c[i]]+w[i]}初次优化后 procedure ZeroOnePack(cost,weight) for v=V..cost f[v]=max{f[v],f[v-cost]+weight} for i=1..N ZeroOnePack(c[i],w[i]) 实际上，这里的下限还可以优化 for i=1..n bound=max{V-sum{c[i..n]},c[i]} //f[v] <- f[v-c[i] <- f[v-c[i]-c[i-1]] <- f[v-c[i]-c[i-1] - c[i-2]] <- f[v-sum{c[i..n] （现在真是天下文章一大抄，第一个作者有可能手误写错了，后面的博客全是错的，虽然我也参考了别人写的，但认真思考是很重要的的）。从另一个方面来考虑，当V很大的时候，根本就不需要规划，直接装。当你很有钱的时候，买东西是不是很随意 for v=V..bound
public class Simple01Bag {
/**
* 二维数组表示
*
* @param c
* @param w
* @param v
* @return
*/
private static int[][] simple01Bag_1(int[] c, int[] w, int v) {
if (c.length != w.length) throw new IllegalArgumentException();
int[][] f = new int[c.length + 1][v + 1];
//初始化
for (int col = 0; col <= v; col++) {
f[0][col] = 0;
}
//初始化
for (int col = 0; col <= c.length; col++) {
f[col][0] = 0;
}
for (int i = 1; i <= c.length; i++) {
for (int j = 1; j <= v; j++) {
if (j < c[i - 1]) f[i][j] = f[i - 1][j]; //这里是c[i-1],因为我们的数组起始索引是0
else f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - c[i - 1]] + w[i - 1]); //这里是w[i-1],因为我们的数组起始索引是0
}
}
//看看选择的是哪些
int[] flag = new int[c.length + 1];
for (int i = c.length; i > 0; i--) {
if (f[i][v] > f[i - 1][v]) {
flag[i - 1] = 1; //这里是flag[i-1],因为我们的数组起始索引是0
v -= c[i - 1]; //这里是c[i-1],因为我们的数组起始索引是0
}
}
for (int i = 0; i < c.length; i++) {
System.out.println(flag[i]);
}
return f;
}
/**
* 一维数组表示 path[][]计算加入物品
*
* @param c
* @param w
* @param v
* @return
*/
private static int[] simple01Bag_2(int[] c, int[] w, int v) {
if (c.length != w.length) throw new IllegalArgumentException();
int[] f = new int[v + 1];
int[][] path = new int[c.length + 1][v + 1];
int bound = 0;
//初始下限
for (int i = 0; i < c.length; i++) {
bound += c[i];
}
// f[v] <- f[v-c[i] <- f[v-c[i]-c[i-1]] <- f[v-c[i]-c[i-1] - c[i-2]] <- f[v-sum{c[i..n]
for (int i = 0; i < c.length; i++) {
for (int j = v; j >= Math.max(v - bound, c[i]); j--) {
// f[j] = Math.max(f[j], f[j - c[i]] + w[i]);
if (f[j] < f[j - c[i]] + w[i]) {
f[j] = f[j - c[i]] + w[i];
path[i][j] = 1;
}
}
bound -= c[i];
}
int i = c.length;
int j = v;
//打印出选择的物品
while (i >= 0 && j >= 0) {
if (path[i][j] == 1) {
System.out.println(i + "____" + c[i]); // i=0..(c.length-1)
j -= c[i];
i--;
} else {
i--;
}
}
return f;
}
//test
public static void main(String[] args) {
int[] c = {2, 2, 6, 5, 4};
int[] w = {6, 3, 5, 4, 6};
int[] f = simple01Bag_2(c, w, 10);
for (int j = 0; j <= 10; j++) {
System.out.print(f[j] + " - ");
}
System.out.println();
int[][] ss = simple01Bag_1(c, w, 10);
for (int i = 0; i <= c.length; i++) {
for (int j = 0; j <= 10; j++) {
System.out.print(ss[i][j] + " - ");
}
System.out.println();
}
}
}
完全背包问题
- 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：
f[i][v]=max{f[i-1][v-kc[i]]+kw[i] | 0<=kc[i]<=v}
求解状态f[i][v]的时间是O(v/c[i])，总的复杂度可以认为是O(VΣ(V/c[i]))，是比较大的 - 简单优化
首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的那个
若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j]，则将物品j去掉 - 一维数组优化
for i=1..N
for v=cost..V
f[v]=max{f[v],f[v-cost]+weight}
下面是代码，completeBag使用一维数组，preOperate尝试丢掉一些不可能装入背包的数据。（注意看注释）
public class CompleteBag {
public static int[] completeBag(int[] c, int[] w, int v) {
if (c.length != w.length) throw new IllegalArgumentException();
int[][] path = new int[c.length + 1][v + 1]; //保存添加的物品
int[] f = new int[v + 1];
for (int i = 0; i < c.length; i++) {
for (int j = c[i]; j <= v; j++) {
if (f[j] < f[j - c[i]] + w[i]) {
f[j] = f[j - c[i]] + w[i];
path[i][j] = 1;
}
}
}
int i = c.length;
int j = v;
//打印添加的物品,注意和简答背包一维数组的区别
while (i >= 0 && j >= 0) {
if (path[i][j] == 1) {
System.out.println(i + "____" + c[i]);
j -= c[i];
} else {
i--;
}
}
return f;
}
/**
* 可以丢掉很多数据
* @param c
* @param w
* @param v
*/
public static int[] preOperate(int[] c, int[] w, int v){
boolean[] flag = new boolean[c.length];
int count = 0;
//去掉c[i] > v或者c[i] <= c[j] && w[i] >= w[j]的数据
for(int i = 0;i < c.length ; i++){
if(c[i] > v) {
flag[i] = true;
count++;
continue;
}
for(int j = i + 1;j < w.length;j++){
if(c[i] <= c[j] && w[i] >= w[j]){
flag[j] = true;
count++;
}
}
}
ArrayList<Integer> newC = new ArrayList<>();
ArrayList<Integer> newW = new ArrayList<>();
//一开始java代码没有想好,写的稍微有点复杂
for(int i = 0;i < flag.length; i++){
System.out.println(flag[i] + " " + count);
if(!flag[i]){
newC.add(c[i]);
newW.add(w[i]);
}
}
int[] newc = new int[flag.length - count];
// System.arraycopy(newC,0,newc,0,newc.length);
int[] neww = new int[flag.length - count];
// System.arraycopy(newW,0,neww,0,newc.length);
for(int i = 0;i < newc.length; i++){
newc[i] = newC.get(i);
neww[i] = newW.get(i);
}
// for(int i = 0;i < newc.length; i++){
// System.out.println(newc[i] + " " +neww[i]);
// }
int[] ss = completeBag(newc,neww,v);
// for (int i = 0; i <= v; i++) {
// System.out.print(ss[i] + " - ");
// }
return ss;
}
public static void main(String[] args) {
int[] c = {5, 2, 6, 5, 3};
int[] w = {6, 3, 5, 4, 6};
int v = 10;
// int[] ss = completeBag(c, w, v);
// for (int i = 0; i <= v; i++) {
// System.out.print(ss[i] + " - ");
// }
int[] ss = preOperate(c, w, v);
for (int i = 0; i <= v; i++) {
System.out.print(ss[i] + " - ");
}
}
}
