多重背包问题
考虑最一般形式的背包问题(动态规划算法),如下:
输入一个整数W和V,W和V代表背包可容纳的最大重量和最大体积;
输入N个整数,代表N种物品;每个物品有4种属性,分别是重量、体积、价值、数量;
以下依次输入的N行数,每行的四个数分别代表四种属性;
求可以获得的最大价值;
sample input:
215 130
10
12 9 16 4
16 4 5 4
15 12 11 3
7 17 5 2
12 9 16 4
13 2 17 1
19 14 6 5
9 8 1 2
14 8 6 5
18 1 12 3
sample output:
219
//s 数组存储了物品的四个属性,w,v分别为最大载重和最大容纳的体积
1.最为基本的考虑方式是使用一个三维数组来存储:
f[i][j][k]表示考虑前i个物品,背包载重为j,容纳体积为k时可获得的最大价值
public static int F(int[][] s, int w, int v, int n){
int[][][] f = new int[n + 1][w + 1][v + 1];
int i, j, k, r;
for(i = 1; i <= n; i ++){
for(j = 1; j <= w; j++){
for(k = 1; k <= v; k ++){
for (r = 0; r <= s[i - 1][3] && j - r * s[i - 1][0] >= 0 && k - r * s[i - 1][1] >= 0; r++) {
f[i][j][k] = Math.max(f[i - 1][j][k], f[i - 1][j - r * s[i - 1][0]][k - r * s[i - 1][1]] + s[i - 1][2] * r);
}
}
}
}
2、上述方式的内存占用较大,发现迭代时只用了前一组数据和当前的数据,故可以考虑如下的简化:
倒序遍历时之前的数据还没被更新,不用额外去存储一次
public static int H(int[][] s, int w, int v, int n){
int[][] f = new int[w + 1][v + 1];
int i, j, k, r;
for(i = 1; i <= n; i ++){
for(j = w; j >=0; j --) {
for (k = v; k >= 0; k--) {
r = 0;
while (r <= s[i - 1][3] && j - r * s[i - 1][0] >= 0 && k - r * s[i - 1][1] >= 0) {
f[j][k] = Math.max(f[j][k], f[j - r * s[i - 1][0]][k - r * s[i - 1][1]] + s[i - 1][2] * r);
r ++;
}
}
}
}
return f[w][v];
}
3、对于数据量较大的问题,2中代码运行相对较慢,故考虑用二进制优化
获取输入并存储物品属性的时候改用Arraylist,方便进行二进制优化
Scanner input = new Scanner(System.in);
ArrayList<int[]> tab = new ArrayList<>();
int W = input.nextInt();
int V = input.nextInt();
int n = input.nextInt();
int num, t;
int[] p = new int[3];
for(int i = 0; i < n; i ++){
for(int j = 0; j < 3; j ++)
p[j] = input.nextInt();
num = input.nextInt();
t = 1;
while(num - t > 0){
int[] temp = new int[3];
for(int k = 0; k < 3; k ++)
temp[k] = p[k] * t;
tab.add(temp);
num -= t;
t <<= 1;
}
if(num - t <= 0){
int[] temp = new int[3];
for(int k = 0; k < 3; k ++)
temp[k] = p[k] * num;
tab.add(temp);
}
}
input.close();
进一步的DP计算:
public static int F(ArrayList<int[]> s, int w, int v){
int[][] f = new int[w + 1][v + 1];
int i, j;
for(int[] p : s){
for(i = w; i >= 0; i --){
for(j = v; j >= 0; j--){
if(i - p[0] >=0 && j - p[1] >=0)
f[i][j] = Math.max(f[i][j], f[i - p[0]][j - p[1]] + p[2]);
}
}
}
return f[w][v];
}
//二进制优化的想法来源于其他大佬,笔者发现网上绝大多数是c++代码,没有发现java版本的,故尝试写了个java版本的