首页 > 编程笔记 > Java笔记 阅读：37

部分背包问题（贪心算法，Java实现）

有 n 个物品，第 i 个物品的重量为 wi，价值为 vi，在不超过背包重量 c 的情况下，使装入背包的总价值尽可能高，每个物品的重量和价值均匀分布，可拆分装入背包，价值和重量按比例计算。

例如，背包容量为 80，有 3 个物品，每个物品的重量和价值如下表所示。


表 1 物品的重量和价值

输出装入背包的最佳方案。

根据贪心选择策略，要使装入背包的物品总价值最大，需要先装入价值大的物品，再装入价值小的物品，这就需要计算每个物品的单位重量价值，并按单位重量价值从大到小排序，然后依次选择物品装入背包，这样装入背包的价值就会达到最大。

具体步骤是，首先计算每种物品的单位重量价值 valuei/weighti，然后，按照贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未达到 c，则选择单位重量价值次高的物品并尽可能多地装入背包。根据以上策略重复执行，直到背包装满为止。

表 1 中物品的单位重量价值如下表所示：


表 2 物品的重量、价值和单位重量价值

选择物品装入背包的顺序应该是第 2 个物品、第 3 个物品和第 1 个物品：
算法实现如下： 
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);
    }
}

相关文章