|
01背包：一个旅行者有一个最多能装 M 公斤的背包，现在有 nn件物品，它们的重量分别是W1，W2，...,Wn它们的价值分别为v1,v2,...,vnv1,求旅行者能获得最大总价值。
注：0-1背包问题指的是每个物品只能使用一次
输入
10 4
2 1
3 3
4 5
7 9
直接上代码注释分析：
import java.util.Scanner;
public class 背包问题 {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int m=scanner.nextInt();//容量
int n=scanner.nextInt();//物品数
int v[]=new int[100];//物品的价值
int w[]=new int[100];//物品的重量
int f[][]=new int[100][100];//f[][]的值代表的是物品的价值
for (int i=1;i<=n;i++){
w[i]=scanner.nextInt();//第i个物品的重量
v[i]=scanner.nextInt();//第i个物品的价值
}
for (int i=1;i<=n;i++){//i是物品个数的增加
for (int j=1;j<=m;j++){//j是背包容量的增加
f[i][j]=f[i-1][j];//先用上一个背包容量装的物品
if(j>=w[i]){//背包容量能否装第i个物品
f[i][j]=Math.max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
//01背包每个物品只能取一个
//于是每次与上次（i-1）装好物品的同一容量级别（j）背包比较,
//谁价值更大用谁(即装了第i个物品后是否价值变大了)
//j-w[i]是此时背包容量减去此时i的物品重量
//f[i-1][j-w[i]]从上次物品i-1行中选，
//除去第i个物品重量后最多价值能装的位置
//f[i-1][j-w[i]]+v[i]最后再加上第i个物品的价值v[i]
}
}
}
for (int i=0;i<=n;i++){
for (int j=0;j<=m;j++){
System.out.print(f[i][j]);//打印价值数组
System.out.print(" ");
}
System.out.println();}
}
}
补充：f数组的f[i]是能存放第i个物品时的结果，f[i][j]是能存放第i个物品时，第j大小的背包容量
输出：
0 0 0 0 0 0 0 0 0 0 0?
0 0 1 1 1 1 1 1 1 1 1?
0 0 1 3 3 4 4 4 4 4 4?
0 0 1 3 5 5 6 8 8 9 9?
0 0 1 3 5 5 6 9 9 10 12?
完全背包问题：
只需要修改为
f[i][j-w[i]]+v[i]
具体推算过程如下：
f[i][j]=Math.max(f[i-1][j],f[i][j-w[i]]+v[i]);
//f(i,j) = max(f(i-1,j),f(i-1,j-vi)+Wi,…,f(i-1,j-kVi)+kWi)
//完全背包每次取的物品数数量可以无限
//f(i,j-vi) = max(f(i-1,j-Vi),f(i-1,j-2Vi)+Wi,…,f(i-1,j-kVi)+kWi)
//立即推：f(i,j) = max(f(i-1,j),f(i,j-Vi)+Wi)
输出
0 0 0 0 0 0 0 0 0 0 0?
0 0 1 1 2 2 3 3 4 4 5?
0 0 1 3 3 4 6 6 7 9 9?
0 0 1 3 5 5 6 8 10 10 11?
0 0 1 3 5 5 6 9 10 10 12?
|