Java初解背包问题
经典背包问题：
有n个重量和价值分别为w和v的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
限制条件： 1<= n <=100
1<=w,v,<=100
1<= W <=1000
样例：
输入：
n=4 {w,v} = {{2,3},{1,2},{3,4},{2,2}} W = 5
输出：
7
解法一：
针对每个物品是否放入背包进行搜索试试
代码：
package thebackage;
/*
* 背包问题解法一
*/
public class FirstB {
int AW = 0;
int n;
int[] weight;
int[] value;
public FirstB(int n,int[] weight,int[] value) {
this.n = n;
this.weight = weight;
this.value = value;
}
public int FtheMax(int i,int j) {
if (n==i) {
//没有剩余物品
AW=0;
} else if(weight[i]>j){
//无法挑选这个物品
AW=FtheMax(i+1, j);
} else {
//在挑选和不挑选进行搜索
AW=max(FtheMax(i+1, j), FtheMax(i+1,j-weight[i])+value[i]);
}
return AW;
}
public int max(int a,int b) {
if (a>b) {
return a;
}else {
return b;
}
}
public static void main(String[] args) {
int n=4;
int w=5;
int[] value = {3,2,4,2};
int[] weight = {2,1,3,2};
FirstB firstB = new FirstB(n, weight, value);
System.out.println(firstB.FtheMax(0, w));
}
}这种解法搜索深度为n，并且每一层都需要两次分支，最坏需要O(2^n)的时间
解法2可以尝试利用记忆化搜索进行优化
先上代码：
package thebackage;
/**
*
* @author linziyu
*优化背包问题
*/
public class SecondB {
int n;
int[] value;
int[] weight;
int values = 0;
int[][] dp = new int[100][100];//进行结果记录
public SecondB(int n,int[] value,int[] weight) {
this.n = n;
this.value = value;
this.weight = weight;
}
public int theBest(int i,int weights) {
if (dp[i][weights]>0) {
//已经计算过的话直接使用之前的结果
return dp[i][weights];
}
if(i==n){
values=0;
} else if (weight[i]>weights) {
values=theBest(i+1, weights);
} else {
values=max(theBest(i+1, weights), theBest(i+1,weights-weight[i])+value[i]);
}
//将结果记录在数组中
return dp[i][weights]=values;
}
public int max(int a,int b) {
if (a>b) {
return a;
} else {
return b;
}
}
public static void main(String[] args) {
int n=4;
int w=5;
int[] value = {3,2,4,2};
int[] weight = {2,1,3,2};
SecondB secondB = new SecondB(n, value, weight);
System.out.println(secondB.theBest(0,w));
}
}此优化可以使得对于同样的参数，只会在第一次被调用到时执行递归部分，第二次之后都会直接返回，参数组合不过nW中， 所以只需O(nW)的复杂度就可以解决。