首页 > 代码库 > 背包问题
背包问题
先来个0-1背包问题，设置背包总共能容纳的重量是100kg,当前给定有5个物品，它们的重量和价值分别存在数组w和v上（注意：为了方便，我把这两个数组的第一位的值设为0，即实际数组大小为6），并存储了每个物品是否被装包的情况，我们先来看他的Java实现。
package com.algorithm.impl;
import java.util.Arrays;
public class Knapsack {
public static void main(String[] args){
int[] w = {0, 25, 40, 10, 48, 27};
int[] v = {0, 32, 45, 21, 53, 40};
int res = knapsack(100, w, v);
System.out.println("包的最大价值为： " + res);
}
public static int knapsack(int maxw, int[] w, int[] v){
int num = w.length - 1;
//保存结果
int[][] f = new int[num + 1][maxw + 1];
//保存每个物体是否装包
int[][] s = new int[num + 1][maxw + 1];
for(int i = 0; i < f.length; i++)
Arrays.fill(f[i], 0);
//物品种类为num
for(int n = 1; n <= num; n++){
//设置可接受的重量值
for(int x = 1; x <= maxw; x++){
//设置对于物品n可以最多容纳多少个，因为这是0-1背包，所以非1即0，这是通过重量而得出的
int maxn = 1;
if(w[n] > x) maxn = 0;
for(int i = 0; i <= maxn; i++){
//如果当前的结果可以使背包有更高的价值，那么添加上去
if(f[n][x] < f[n - 1][x - w[n] * i] + i * v[n]){
f[n][x] = f[n - 1][x - w[n] * i] + i * v[n];
s[n][x] = i;
}
}
}
}
int result = 0;
int xx = 0;
//获取最大值
for(int i = 0; i <= maxw; i++){
if(f[num][i] > result){
result = f[num][i];
xx = i;
}
}
//输出每种物品是否装包的情况
for(int i = num; i >= 1; i--){
System.out.println("物品" + i +"： " + s[i][xx]);
xx -= s[i][xx] * w[i];
}
return result;
}
}
运行结果为：
物品5： 1 物品4： 1 物品3： 0 物品2： 0 物品1： 1 包的最大价值为： 125
小明去旅游需要带上一些物品，有5种物品供选择，每种物品的体积，重量，数量，价值分别如下：
物品编号 体积 (cm3) 重量 (KG) 数量 价值
1 30 3 10 4
2 50 8 10 5
3 10 2 10 2
4 23 5 8 3
5 130 20 5 11
现在限制总的体积最多为500 cm3，总的重量最多为100 KG，请问小明能带上的物品的最大总价值是多少？
分析：本题是著名的背包问题。首先我们定义一些变量，记v[i]为第i个物品的体积，w[i]为第i个物品的重量，c[i]为第i个物品的数量，t[i]为第i个物品的价值，i＝1，2，3，4，5。
我们可以假设物品就是按编号顺序来选择的，某个物品不被选上可看作被选用了0个。这样的话，我们的问题就是在5种物品里选择，以满足重量体积限制，并使总价值最大。按顺序在5种物品里选可以分解为先在前4种物品里选，最后确定最后一种物品怎么选，一般地，要在前n种物品里选，可以先看作在前n-1种物品里选，最后选第n种，但我们要用一个状态（也就是子问题）来记录前n-1种物品选择的状态，目标是使目标问题能递归的分解成子问题，但要注意状态数目不能太多，否则内存可能不够。
我们定义子问题如下：在前n种物品里选择，满足总体积为x和总重量为y的条件下，总价值最多是多少？记这个最大总价值为f(n,x,y). 根据这个定义, 原问题就是求f(5,500,100).
当我们求f(n,x,y)的时候, 可以先考虑第n个物品的选择,假设它被选用i个,那么前面它的总体积为i*v[n], 总重量为i*w[n], 于是前(n-1)个物品的总体积为x-i*v[n], 总重量为y-i*w[n], 于是f(n,x,y)归约为f(n-1, x-i*v[n], y-i*w[n]), 而这个i的取值限制为i>=0, i<=c[n], x-i*v[n]>=0,y-i*w[n]>=0. 即:
f(n,x,y)= MAX{ f(n-1, x-i*v[n], y-i*w[n]) + i*t[n] }
代码如下:package com.algorithm.impl;
import java.util.Arrays;
public class Knapsack02 {
public static void main(String[] args){
int[] v = {0, 30, 50, 10, 23, 130}; //体积
int[] w = {0, 3, 8, 2, 5, 20}; //重量
int[] c = {0, 10, 10, 10, 8, 5}; //数量
int[] t = {0, 4, 5, 2, 3, 11}; //价值
int res = knapsack(500, 100, v, w, c, t);
System.out.println("包的最大价值为： " + res);
}
public static int knapsack(int maxx, int maxy, int[] v, int[] w, int[] c, int[] t){
int num = v.length - 1;
//保存结果
int[][][] f = new int[num + 1][maxx + 1][maxy + 1];
//保存每个物体的装包数量
int[][][] s = new int[num + 1][maxx + 1][maxy + 1];
for(int i = 0; i < f.length; i++)
for(int j = 0; j < f[i].length; j++)
Arrays.fill(f[i][j], 0);
for(int i = 0; i < s.length; i++)
for(int j = 0; j < s[i].length; j++)
Arrays.fill(s[i][j], 0);
//物品种类为num
for(int n = 1; n <= num; n++){
//设置可接受的体积
for(int x = 1; x <= maxx; x++){
//设置可接受的重量
for(int y = 1; y <= maxy; y++){
//设置对于物品n可以最多容纳多少个，这是通过体积和重量的双重限制而得出的
int maxn = c[n];
if(x / v[n] < maxn) maxn = x / v[n];
if(y / w[n] < maxn) maxn = y / w[n];
for(int i = 0; i <= maxn; i++){
//如果当前的结果可以使背包有更高的价值，那么添加上去
if(f[n][x][y] < f[n - 1][x - v[n] * i][y - w[n] * i] + i * t[n]){
f[n][x][y] = f[n - 1][x - v[n] * i][y - w[n] * i] + i * t[n];
s[n][x][y] = i;
}
}
}
}
}
int result = 0;
int xx = 0, yy = 0;
//获取最大值
for(int i = 0; i <= maxx; i++){
for(int j = 0; j <= maxy; j++){
if(f[num][i][j] > result){
result = f[num][i][j];
xx = i;
yy = j;
}
}
}
//输出每种物品的装包数量
for(int i = num; i >= 1; i--){
int temp = s[i][xx][yy];
System.out.println("物品" + i +"的数量为： " + s[i][xx][yy]);
xx -= temp * v[i];
yy -= temp * w[i];
}
return result;
}
}
运行结果为：物品5的数量为： 0 物品4的数量为： 4 物品3的数量为： 10 物品2的数量为： 0 物品1的数量为： 10 包的最大价值为： 72
背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。