[算法]用java实现0-1背包和部分背包问题

问题描述：
0-1背包问题，部分背包问题（课本P229）
实验要求：
（1）实现0-1背包的动态规划算法求解
（2）实现部分背包的贪心算法求解

0-1背包问题代码：

    public static void main(String[] args){
        //获取物品个数，每个物品的重量和价值，以及背包容量
        Scanner in1 = new Scanner(System.in);
        System.out.println("请输入物品个数和背包容量:");
        int num_goods = in1.nextInt();
        int capacity = in1.nextInt();
        System.out.println("请输入1-"+num_goods+"的物品重量和价值:");
        int[] weight = new int[num_goods+1];
        int[] value = new int[num_goods+1];
        Scanner in2 = new Scanner(System.in);
        for(int i = 1;i<=num_goods;i++){
            weight[i] = in2.nextInt();
            value[i] = in2.nextInt();
        }
        in1.close();
        in2.close();
        //动态规划
        int[][] f = new int[num_goods+1][capacity+1];   //f[i][j]表示容量为j的背包前i个物品的总价值
        
        for(int i = 1;i<=num_goods;i++){
            for(int j = 1; j<=capacity; j++){
                if(weight[i] > j){
                    f[i][j] = f[i-1][j];
                }else {
                    int x = f[i-1][j];
                    int y = f[i-1][j-weight[i]] +value[i];
                    f[i][j] = x>y?x:y;
                }
            }            
        }
        //输出结果
        for(int i = 0;i<= num_goods;i++){
            for(int j = 0;j<=capacity;j++){
                System.out.print(f[i][j]+"\t");
                if(j == capacity){
                    System.out.print("\n");
                }
            }
        }
        int j = capacity;
        int total_value = 0;
        int total_weight = 0;
        for(int i = num_goods;i>=1;--i){
            if(j>0){
                if(j-weight[i] >=0){
                    if(f[i][j] == (f[i-1][j-weight[i]]+value[i])){
                        System.out.println("选取物品:"+i+"重量为:"+weight[i]+"价值为:"+value[i]);
                        j -= weight[i];
                        total_value += value[i];
                        total_weight  += weight[i];
                    }
                    System.out.println("总价值为:"+total_value+"\t总重量为:"+total_weight);
                }
            }
        }
    }

二：部分背包

    public class Goods{
        int weight;
        int value;
        float value_per_weight;     //value/weight
        float load;  //占比系数
        
    }
    //快排
    public static void QuickSort(Goods []A,int l,int r){
        Goods temp;
        int i = l;
        int j = r;
        if(l<r){
            temp = A[i];
            while(i != j){
                while(i<j && A[j].value_per_weight <= temp.value_per_weight){
                    --j;
                }
                A[i] = A[j];
                while(i<j && A[i].value_per_weight >= temp.value_per_weight){
                    ++i;
                }
                A[j] = A[i];
            }
            A[i] = temp;
            QuickSort(A, l, i-1);
            QuickSort(A, i+1, r);
        }
    }
    //贪心算法
    public static void Greedy(Goods[] goods,int capacity,int num_goods){
        for(int i = 0; i<num_goods; i++){
            if(goods[i].weight<capacity){
                capacity -= goods[i].weight;
                goods[i].load = 1;
            }else if(capacity>0){
                goods[i].load = ((float)capacity/(float)goods[i].weight);
                capacity = 0;
                break;
            }
        }
    }
    public static void main(String[] args){
        float total_value = 0 ;
        float total_weight  = 0;
        //获取物品个数，每个物品的重量和价值，以及背包容量
        Scanner in1 = new Scanner(System.in);
        System.out.println("请输入物品个数和背包容量:");
        int num_goods = in1.nextInt();
        int capacity = in1.nextInt();
        System.out.println("请输入1-"+num_goods+"的物品重量和价值:");
        Goods[] goods = new Goods[num_goods];
        Scanner in2 = new Scanner(System.in);
        for(int i = 0;i<num_goods;i++){
            goods[i] = new part_of_package_greedy().new Goods();;
            goods[i].weight = in2.nextInt();
            goods[i].value= in2.nextInt();
            goods[i].value_per_weight = (goods[i].value)/(goods[i].weight);
        }    
        in1.close();
        in2.close();
        QuickSort(goods,0,(num_goods-1));
        //执行贪心算法
        Greedy(goods, capacity, num_goods);
        System.out.println("执行贪心算法求得部分背包解为:");
        for(int i = 0;i<num_goods;i++){
            System.out.println("重量为:"+goods[i].weight+"\t价值为:"+goods[i].value+"\t装载率为:"+goods[i].load);
            total_value+=goods[i].value*goods[i].load;
            total_weight+=goods[i].weight*goods[i].load;
        }
        System.out.println("背包容量:"+capacity+"\t背包装入重量:"+total_weight+"\t装入总价值:"+total_value);
    }