部分背包问题(贪心算法,Java实现)
有 n 个物品,第 i 个物品的重量为 wi,价值为 vi,在不超过背包重量 c 的情况下,使装入背包的总价值尽可能高,每个物品的重量和价值均匀分布,可拆分装入背包,价值和重量按比例计算。
例如,背包容量为 80,有 3 个物品,每个物品的重量和价值如下表所示。

表 1 物品的重量和价值
输出装入背包的最佳方案。
根据贪心选择策略,要使装入背包的物品总价值最大,需要先装入价值大的物品,再装入价值小的物品,这就需要计算每个物品的单位重量价值,并按单位重量价值从大到小排序,然后依次选择物品装入背包,这样装入背包的价值就会达到最大。
具体步骤是,首先计算每种物品的单位重量价值 valuei/weighti,然后,按照贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未达到 c,则选择单位重量价值次高的物品并尽可能多地装入背包。根据以上策略重复执行,直到背包装满为止。
表 1 中物品的单位重量价值如下表所示:

表 2 物品的重量、价值和单位重量价值
选择物品装入背包的顺序应该是第 2 个物品、第 3 个物品和第 1 个物品:
算法实现如下:
在求解背包问题的过程中,需要根据物品的重量、价值和单位重量价值来确定是否要装入背包,这里采用 Bag 类来表示物品的属性信息。
上面的背包问题 Knapsack() 也可以使用递归的方式实现:
例如,背包容量为 80,有 3 个物品,每个物品的重量和价值如下表所示。

表 1 物品的重量和价值
输出装入背包的最佳方案。
根据贪心选择策略,要使装入背包的物品总价值最大,需要先装入价值大的物品,再装入价值小的物品,这就需要计算每个物品的单位重量价值,并按单位重量价值从大到小排序,然后依次选择物品装入背包,这样装入背包的价值就会达到最大。
具体步骤是,首先计算每种物品的单位重量价值 valuei/weighti,然后,按照贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未达到 c,则选择单位重量价值次高的物品并尽可能多地装入背包。根据以上策略重复执行,直到背包装满为止。
表 1 中物品的单位重量价值如下表所示:

表 2 物品的重量、价值和单位重量价值
选择物品装入背包的顺序应该是第 2 个物品、第 3 个物品和第 1 个物品:
- 由于背包容量为 80,此时 30<80,因此可将第 2 个物品装入背包;
- 然后尝试装入第3个物品,由于 30+40<80,因此可将第 3 个物品装入背包,此时背包的总重量为 70,剩余容量为 10,物品总价值为 310;
- 尝试将第 1 个物品装入背包,但是2 0>10,第 1 个物品的重量超过了背包的剩余容量,表明不能完全装入背包,但可部分装入背包,装入的比例为 10/20=0.5,即装入一半,其价值为 25,装入第 1个 物品的一半后,则背包中物品的重量为 80,总价值为 335。
算法实现如下:
import java.util.Scanner; class Bag { public int pid; //物品编号 public int weight; //重量 public int value; //价值 public float wi; //单位重量价值 float x; public Bag(int pid,int w,int v) { this.pid=pid; this.weight=w; this.value=v; this.wi=(float)value/weight; } } public class KnapsackGreedy { public void Sort(Bag[] item) //将物品按单位重量价值从大到小排序 { Bag t; int i,j,k; for(i=0;i<item.length;i++) { k=i; t=item[i]; for(j=i+1;j<item.length;j++) { if(t.wi<item[j].wi) { t=item[j]; k=j; } } t=item[i]; item[i]=item[k]; item[k]=t; } } public void Knapsack(Bag[] p,int c,int n) //背包问题 { float cleft=c,cmax=0.0f; int i=0; while(i<n && p[i].weight<=cleft) { cleft-=p[i].weight; cmax+=p[i].value; System.out.println("第"+p[i].pid+"个物品全部装入,当前背包价值为"+cmax); p[i].x=1.0f; i++; } if(i<n) { float a= (float) (cleft*p[i].wi) ; //当前价值 p[i].x=cleft/p[i].weight; cmax+=cmax+a; System.out.printf("第%d个物品装入了%.2f,当前背包价值为%.1f\n",p[i].pid,cleft/p[i].weight,cmax); } } public static void main(String args[]) { int pid; int weight; int value; KnapsackGreedy Knap=new KnapsackGreedy(); Scanner sc = new Scanner(System.in); System.out.println("请输入物品的个数和背包的容量:"); int n=sc.nextInt(); //物品的个数 int c=sc.nextInt(); //背包的容量 Bag[] p=new Bag[n]; System.out.println("请依次输入各个物品的重量 w 和价值 v"); for(int i=0;i<n;i++) { pid=i+1; weight=sc.nextInt(); value=sc.nextInt(); p[i]=new Bag(pid,weight,value); } Knap.Sort(p); //Knap.Knapsack2(p,0,c,0.0); Knap.Knapsack(p,c,n); for(int i=1;i<=n;i++) { for(int j=0;j<n;j++) { if (i == p[j].pid) System.out.printf("%.2f ",p[j].x); } } } }程序运行结果如下:
请输入物品的个数和背包的容量:
3 80
请依次输入各个物品的重量w和价值v
20 50
30 150
40 160
第2个物品全部装入,当前背包价值为150.0
第3个物品全部装入,当前背包价值为310.0
第1个物品装入了0.50,当前背包价值为335.0
0.50 1.00 1.00
在求解背包问题的过程中,需要根据物品的重量、价值和单位重量价值来确定是否要装入背包,这里采用 Bag 类来表示物品的属性信息。
class Bag { public int pid; //物品编号 public int weight; //重量 public int value; //价值 public float wi; //单位重量价值 float x; public Bag(int pid,int w,int v) { this.pid=pid; this.weight=w; this.value=v; this.wi=(float)value/weight; } }为了方便其他方法存取,物品的各个属性信息定义为 public,当然也可以定义为 private,增加一些关于各个属性的 get 和 set 方法即可。
上面的背包问题 Knapsack() 也可以使用递归的方式实现:
public void Knapsack2(Bag[] p,int k,int c,double v) //背包问题的递归算法实现 { if(p[k].weight<c) { v=v+p[k].value; System.out.println("第"+p[k].pid+"个物品全部装入,当前背包价值为"+v); c=c-p[k].weight; Knapsack2(p, k+1, c, v); } else { double a=c*p[k].wi;//当前价值 v=v+a; System.out.println("第"+p[k].pid+"个物品装入了"+((float)c/p[k].weight)+",当前背包价值为"+v); } }