01背包问题
public class KnapsackProblem {
public static void main(String[] args) {
int []w={1,2,3,4,5};
int[]value={3,4,6,8,10};
int capacity=10;
int n=w.length;
ZeroOneKnapsack(w,value,n,capacity);
}
/**
*
* @param w 重量
* @param value 价值
* @param n 种类
* @param capacity 容量
*/
public static void ZeroOneKnapsack(int[]w,int[]value,int n,int capacity){
//因为第一行均为0,所以要加1
//第一行和第一列我们都不会用到,目的是为了更好的理解01背包
int[][]v=new int[n+1][capacity+1];
//因为v[0][j]和v[i][0]不处理默认为0
//记录路径
int [][]path=new int[n+1][capacity+1];
for (int i = 1; i < n+1; i++) {
for (int j = 1; j < capacity+1; j++) {
if(w[i-1]>j){
//如果背包的容量小于当前商品的重量7
v[i][j]=v[i-1][j];
}else {
if(v[i-1][j]<value[i-1]+v[i-1][j-w[i-1]]){
v[i][j]=value[i-1]+v[i-1][j-w[i-1]];
path[i][j]=1;
}else {
v[i][j]= v[i-1][j];
}
}
}
}
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < capacity+1; j++) {
if(v[i][j]<10){
System.out.print(v[i][j]+" ");
}else {
System.out.print(v[i][j]+" ");
}
}
System.out.println();
}
for (int i = 0; i < n+1; i++) {
for (int j = 0; j < capacity+1; j++) {
System.out.print(path[i][j]+" ");
}
System.out.println();
}
int i=path.length-1;
int j=path[0].length-1;
while (i>0&&j>0){
if(path[i][j]==1){
System.out.println("商品"+i+"放入背包");
//这里是和之前一样,我放入背包一件商品,那么我的容量也要对应的减少
//不可能说我容量为20,容量不减少,那么就会重复
j-=w[i-1];
}
i--;
}
/* return v[n+1][capacity];*/
}
}
0 0 0 0 0 0 0 0 0 0 0
0 3 3 3 3 3 3 3 3 3 3
0 3 4 7 7 7 7 7 7 7 7
0 3 4 7 9 10 13 13 13 13 13
0 3 4 7 9 11 13 15 17 18 21
0 3 4 7 9 11 13 15 17 19 21
0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0
商品4放入背包
商品3放入背包
商品2放入背包
商品1放入背包
输出结果如上
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
