Greedy method / non 01 knapsack problem

knapsack problem

The problem is not 01 knapsack problem ,01 Backpack problem items can not be loaded into a part , Or load them all , Or don't load
knapsack problem ： Items can be partially loaded

The law of greed

Greedy rule ： First select the item with the largest value per unit weight , By analogy
The principle of optimality ： Optimal substructure problem , So is the subproblem 01 knapsack problem , Solving a subproblem is equivalent to solving a large problem

01 knapsack

package xcrj.kchalgorithm.greedy;

import java.util.Arrays;

/** *  problem ： *  Yes n Items   The weights are {w1,w2,…,wn}, The values are {v1,v2,…,vn} *  The backpack can bear the weight of w *  Select some items and put them into the backpack  *  Each item can be partially loaded  *  The selected item is required to have the greatest value  * <p> *  Solution ： *  The law of greed  *  Greedy rule ： First select the item with the largest value per unit weight , By analogy  *  The principle of optimality ： Optimal substructure problem , So is the subproblem 01 knapsack problem , Solving a subproblem is equivalent to solving a large problem  */
public class Knapsack {
    
    /* The question says */
    //  Quantity of articles 
    private static int n = 5;
    //  The backpack can bear the weight 
    private static double availableWeight=100.0;

    static class Node implements Comparable<Node> {
    
        //  Item weight 
        private double weight;
        //  Value of goods 
        private double value;
        // value/weight  Unit weight value 
        private double valueWeight;

        /* In reverse order of value per unit weight */
        @Override
        public int compareTo(Node o) {
    
            return this.valueWeight >= o.valueWeight ? -1 : 1;
        }

        @Override
        public String toString() {
    
            return "Node{" +
                    "weight=" + weight +
                    ", value=" + value +
                    ", valueWeight=" + valueWeight +
                    '}';
        }

        public Node() {
    
        }

        public Node(double weight, double value) {
    
            this.weight = weight;
            this.value = value;
            this.valueWeight = value / weight;
        }

        public double getWeight() {
    
            return weight;
        }

        public void setWeight(double weight) {
    
            this.weight = weight;
        }

        public double getValue() {
    
            return value;
        }

        public void setValue(double value) {
    
            this.value = value;
        }

        public double getValueWeight() {
    
            return valueWeight;
        }

        public void setValueWeight(double valueWeight) {
    
            this.valueWeight = valueWeight;
        }
    }

    private static Node[] nodes = {
    new Node(0, 0), new Node(10, 20), new Node(20, 30),
            new Node(30, 66), new Node(40, 40), new Node(50, 60)};

    /* The result shows */
    //  The total accumulated value of the backpack 
    private static double sumValue = 0;
    //  Selected items , You can choose part of 
    private static double[] xs = new double[n + 1];

    public static void knapsack01() {
    
        //  The remaining weight of the backpack 
        double restWeight = availableWeight;
        //  The first i Items 
        int i = 1;
        /*while loop   It can be completely loaded into the backpack */
        //  Greedy rule   goods i It can be fully loaded into the backpack = Remaining capacity of backpack >= The first i The weight of an item 
        while (nodes[i].weight <= restWeight) {
    
            //  I chose the i Items 
            xs[i] = 1.0;
            //  Update the remaining carrying weight of the backpack 
            restWeight -= nodes[i].weight;
            //  Update the total value of items in the backpack 
            sumValue += nodes[i].value;
            //  Load the next item 
            i++;
        }
        /*if Judge   It can be partially loaded into the backpack */
        if (restWeight > 0) {
    
            //  Put things in i Part of 
            xs[i] = restWeight / nodes[i].weight;
            //  Update total value , Load some items , Load a portion of the value 
            sumValue += xs[i] * nodes[i].value;
        }
    }

    public static void main(String[] args) {
    
        System.out.println(" Sort by value per unit weight ：");
        System.out.println(Arrays.toString(nodes));
        System.out.println(" After sorting by value per unit weight ：");
        Arrays.sort(nodes);
        System.out.println(Arrays.toString(nodes));

        knapsack01();
        System.out.println(" Total value ：" + sumValue);
        System.out.println(" Selected items ：" + Arrays.toString(xs));
    }
}