Classic questions: 01 backpack, complete backpack, multiple backpack, two-dimensional cost Backpack

 

 

01 knapsack

 

public class  knapsack 01 {
    public static void main(String[] args) {
        int[] weight = {0, 1, 4, 3};// The weight of the article 
        int[] value = {0, 1500, 3000, 2000};// Unit price of the item 
        int c = 4;// The capacity of the schoolbag 
        dp(weight, value, c);
    }

    public static void dp(int[] weight, int[] value, int c) {
        int n = value.length - 1;// The number of items 
        // A table used to record the process of putting items into a schoolbag 
        //totalValue[i][j] It means before putting i Items , The remaining capacity of the schoolbag is j when , The maximum number of items that can be put in 
        int[][] totalValue = new int[n + 1][c + 1];// Yes n+1 That's ok , Each row has c+1 Elements 
        /*
                    0 pounds      1 pounds      2 pounds      3 pounds      4 pounds 
                    0       0       0       0       0
             guitar     0
             sound     0
             The computer     0
         */
        int[][] result = new int[n + 1][c + 1];// Used to record the process of placing 
        for (int i = 1; i < n + 1; i++) {// Start with the first item and put it on the last item 
            for (int j = 1; j < c + 1; j++) {// When placing an object , The remaining weight from the backpack is 1 Until the remaining weight is 4
                if (weight[i] > j) {// If the weight of the items put in is greater than the remaining weight of the backpack , Can not be put in 
                    totalValue[i][j] = totalValue[i - 1][j];// The total value at this time is equal to the total value of the last time the item was put in 
                } else {
                    if (totalValue[i - 1][j] < value[i] + totalValue[i - 1][j - weight[i]]) {
                        //totalValue[i - 1][j]： The total value of the previous item when it was placed 
                        //value[i-1]： The value of current goods 
                        //totalValue[i-1][j - weight[i-1]]： After putting the current item , The maximum amount of space left to put items in （ Look in the previous line for ）
                        totalValue[i][j] = value[i] + totalValue[i - 1][j - weight[i]];
                        result[i][j] = 1;// This is where the maximum value is stored 
                    } else {
                        totalValue[i][j] = totalValue[i - 1][j];
                    }
                }
            }
        }
        print(totalValue);
        print(result);
        System.out.println(" The greatest value of a backpack is " + totalValue[n][c]);

        //totalValue[n][c] The best condition is the condition in which the goods are put in 
        int i = result.length - 1;
        int j = result[0].length - 1;
        while (i > 0 && j > 0) {
            if (result[i][j] == 1) {
                System.out.print(" The first " + i + " Put two items in your backpack " + "\n");
                j -= weight[i];// Only when we find , Just need to change the capacity of the backpack before continuing to find 
            }
            i--;// Whether you find it or not , All need to step back to the previous line and continue to look 
        }

    }

    public static void print(int[][] arr) {
        for (int[] hang : arr) {
            for (int i : hang) {
                System.out.print(i + "    ");
            }
            System.out.println();
        }
    }

01 Knapsack optimization

public class  knapsack 01 Optimize  {
    public static void main(String[] args) {
        int[] weight = {0, 1, 4, 3};// The weight of the article 
        int[] value = {0, 1500, 3000, 2000};// Unit price of the item 
        int c = 4;// The capacity of the schoolbag 
        youhua1(weight, value, c);
    }


    public static void youhua1(int[] weight, int[] value, int c) {
        int n = value.length - 1;// The number of items 
        int[] totalValue = new int[c + 1];// Scrolling array , Record how the last item was put in 
        int[] temp = new int[c + 1];// Record the status of the current item 
        for (int i = 1; i < n + 1; i++) {// Start with the first item and put it on the last item 
            for (int j = 1; j < c + 1; j++) {// When placing an object , The remaining weight from the backpack is 1 Until the remaining weight is 4
                if (weight[i] > j) {// If the weight of the items put in is greater than the remaining weight of the backpack , Can not be put in 
                    temp[j] = totalValue[j];// The total value at this time is equal to the total value of the last time the item was put in 
                } else {
                    temp[j] = Math.max(totalValue[j], value[i] + totalValue[j - weight[i]]);
                }
            }
            // Every time you put the items , Will the temp[] Reassign to totalValue[]
            for (int x = 0; x < temp.length; x++) {
                totalValue[x] = temp[x];
            }
            System.out.println(Arrays.toString(totalValue));
        }

        System.out.println(" The greatest value of a backpack is " + totalValue[c]);
    }

    public static void youhua2(int[] weight, int[] value, int c) {
        int n = value.length - 1;// The number of items 
        int[] totalValue = new int[c + 1];// Scrolling array , Record how the last item was put in 
        for (int i = 1; i < n + 1; i++) {// Start with the first item and put it on the last item 
            for (int j = c; j >= 1; j--) {// Backward Traversal , Prevent data from being overwritten 
                if (weight[i] <= j) {
                    totalValue[j] = Math.max(totalValue[j], value[i] + totalValue[j - weight[i]]);
                }
            }
            System.out.println(Arrays.toString(totalValue));
        }
        System.out.println(" The greatest value of a backpack is " + totalValue[c]);
    }
}

01 Knapsack variant （ reverse ）

public class  knapsack 01 Variant  {
    public static void main(String[] args) {
        int[] weight = {0, 1, 4, 3};// The weight of the article 
        int[] value = {0, 1500, 3000, 2000};// Unit price of the item 
        int n = 3;// Altogether 3 Items 
        int c = 4;// At least the total weight of the loaded items 
        // The requirement is changed to , At least enough c Heavy objects , The total value of the item is required to be the minimum 
        dp2(weight, value, n, c);
    }

    public static void dp(int[] weight, int[] value, int n, int c) {
        int[][] sum = new int[n + 1][c + 1];
        for (int x = 1; x < c + 1; x++) {// The first 0 The row is initialized to a larger value 
            sum[0][x] = 0x3f3f3f3f;
        }
        for (int i = 1; i < n + 1; i++) {// Start with the first item 
            for (int j = 0; j < c + 1; j++) {// It is possible to load at least... Items 0
                if (weight[i] >= j) {// If the weight of the current item is greater than the current required weight , Either put and only put the current item , Or not 
                    sum[i][j] = Math.min(sum[i - 1][j], value[i]);
                } else {// If the weight of the current item is less than the current required weight 
                    sum[i][j] = Math.min(sum[i - 1][j], value[i] + sum[i - 1][j - weight[i]]);
                }
            }
        }
        System.out.println(sum[n][c]);
//        for (int x = 0; x < sum.length; x++) {
//            for (int y = 0; y < sum[x].length; y++) {
//                System.out.print(sum[x][y] + "\t");
//            }
//            System.out.println();
//        }
    /*
    w  v      0      1       2       3       4
    0  0      0      0x3f    0x3f    0x3f    0x3f
    1  1500   0      1500    0x3f    0x3f    0x3f
    4  3000   0      1500    3000    3000    3000
    3  2000   0      1500    2000    2000    3000
     */
    }

    public static void dp2(int[] weight, int[] value, int n, int c) {
        int[] sum = new int[c + 1];
        for (int x = 1; x < c + 1; x++) {// Initialize to a larger value 
            sum[x] = 0x3f3f3f3f;
        }
        System.out.println(sum);
        for (int i = 1; i < n + 1; i++) {// Start with the first item 
            for (int j = c; j >= 0; j--) {// It is possible to load at least... Items 0
                if (weight[i] >= j) {// If the weight of the current item is greater than the current required weight , Either put and only put the current item , Or not 
                    sum[j] = Math.min(sum[j], value[i]);
                } else {// If the weight of the current item is less than the current required weight 
                    sum[j] = Math.min(sum[j], value[i] + sum[j - weight[i]]);
                }
            }
            System.out.println(Arrays.toString(sum));
        }
        System.out.println(sum[c]);
    }
}

Completely backpack

The number of each item is infinite

public class  Completely backpack  {
    public static void main(String[] args) {
        int[] weight = {0, 1, 4, 3};// The weight of the article 
        int[] value = {0, 1500, 3000, 2000};// Unit price of the item 
        int c = 4;// The capacity of the schoolbag 
        dp2(weight, value, c);
    }

    public static void dp(int[] weight, int[] value, int c) {
        int n = value.length - 1;// The number of items 
        int[] totalValue = new int[c + 1];// Scrolling array , Record how the last item was put in 
        for (int i = 1; i < n + 1; i++) {// Start with the first item and put it on the last item 
            for (int j = c; j >= 1; j--) {// Backward Traversal , Prevent data from being overwritten 
                for (int k = 0; k <= j / weight[i]; k++) {// from 0 Get the maximum value you can get under the current capacity 
                    totalValue[j] = Math.max(totalValue[j], k * value[i] + totalValue[j - k * weight[i]]);
                }
            }
            System.out.println(Arrays.toString(totalValue));
        }
        System.out.println(" The greatest value of a backpack is " + totalValue[c]);
    }

    public static void dp2(int[] weight, int[] value, int c) {
        int n = value.length - 1;// The number of items 
        int[] totalValue = new int[c + 1];// Scrolling array , Record how the last item was put in 
        for (int i = 1; i < n + 1; i++) {// Start with the first item and put it on the last item 
            for (int j = weight[i]; j < c + 1; j++) {// Traversing from front to back , Because the data of this bank will be used 
                // Start pushing where you can put things 
                totalValue[j] = Math.max(totalValue[j], value[i] + totalValue[j - weight[i]]);
            }
            System.out.println(Arrays.toString(totalValue));
        }
        System.out.println(" The greatest value of a backpack is " + totalValue[c]);
    }
}

Multiple backpack

  The simple way

public class  Multiple backpack  {
    public static void main(String[] args) {
        int[] w = {0, 1, 4, 3};// The weight of the article 
        int[] v = {0, 1500, 3000, 2000};// Unit price of the item 
        int[] s = {0, 5, 1500, 800};// Number of each item 
        int c = 10000;// Backpack Capacity 
        dp(w, v, s, c);

    }

    public static void dp(int[] w, int[] v, int[] s, int c) {
        int n = w.length - 1;// How many items are there 
        int[] sum = new int[c + 1];
        for (int i = 1; i < n + 1; i++) {// Start with the first item , To the last item 
            for (int j = c; j >= 1; j--) {// Start with the maximum capacity of the backpack , To capacity 1
                for (int k = 0; k <= s[i] && k * w[i] <= j; k++) {
                    sum[j] = Math.max(sum[j], k * v[i] + sum[j - k * w[i]]);
                }
            }
        }
        System.out.println(sum[c]);
    }

The way to optimize （ Binary system ）

Write your own junk code

public class  Multiple backpack  {
    public static void main(String[] args) {
        int[] w = {0, 1, 4, 3};// The weight of the article 
        int[] v = {0, 1500, 3000, 2000};// Unit price of the item 
        int[] s = {0, 5, 1500, 800};// Number of each item 
        int c = 10000;// Backpack Capacity 
        dp2(w, v, s, c);

    }

    // Binary optimization 
    public static void dp2(int[] w, int[] v, int[] s, int c) {
        int n = w.length - 1;// How many items are there 
        int[] sum = new int[c + 1];
        int n2 = 0;// How many items do you want to split into 
        for (int x = 1; x < n + 1; x++) {
            n2 += depart(s[x])[0];
        }
        int[] w2 = new int[n2 + 1];// Turn into 01 Behind the backpack , Initialize the array of weights 
        int[] v2 = new int[n2 + 1];// Turn into 01 Behind the backpack , Initialize the array of unit prices 
        int m = 0;// Split factor 
        int count = 1;// Record the subscript of the new array 
        for (int x = 1; x < n + 1; x++) {// Traverse the original array 
            // Computation first x How many items can be disassembled 
            int nx = depart(s[x])[0];
            int y=0;
            for (y = 0; y < nx-1; y++) {
                // Whether there is a remainder or not , The front ones are the same 
                m = (int) Math.pow(2, y);
                w2[count] = m * w[x];
                v2[count] = m * v[x];
                count++;
            }
            // If there is a remainder , The last split coefficient is different 
            if(depart(s[x])[1]!=0){
                m=depart(s[x])[1];// Have remainder 
            }else{
                m = (int) Math.pow(2, y);
            }
            w2[count] = m * w[x];
            v2[count] = m * v[x];
            count++;
        }
        for (int i = 1; i < n2 + 1; i++) {// Start with the first item , To the last item 
            for (int j = c; j >= 1; j--) {// Start with the maximum capacity of the backpack , To capacity 1
                if (w2[i] <= j) {
                    sum[j] = Math.max(sum[j], v2[i] + sum[j - w2[i]]);
                }
            
        }
        System.out.println(sum[c]);
    }


    // Calculate an integer n How many can be disassembled 2 Sum of integer powers of , What's the remainder 
    public static int[] depart(int n) {
        int[] arr = new int[2];
        int count = 0;
        int i = 0;
        while (i <= n) {
            i += Math.pow(2, count);
            count++;
        }
        if (i - Math.pow(2, count - 1) < n) {// Have remainder 
            arr[0] = count;// How many numbers 
            arr[1] = n - i +(int) Math.pow(2, count - 1);// remainder 
        } else {
            arr[0]=count-1;// How many numbers 
            arr[1]=0;// remainder 
        }
        return arr;
    }
}

Two dimensional backpack

 

public class  Two dimensional cost backpack  {
    public static void main(String[] args) {
        int[] w = {0, 1, 4, 3};// The weight of the article 
        int[] s = {0, 2, 5, 3};// Volume of items 
        int[] v = {0, 1500, 3000, 2000};// Unit price of the item 
        int n = 3;// The number of items 
        int maxW = 4;// The maximum weight capacity of a schoolbag 
        int maxS = 5;// The maximum volume of the backpack 
        int[][] sum = new int[maxW + 1][maxS + 1];
        for (int x = 1; x < n + 1; x++) {// Start with the first item and put it on the last item 
            for (int i = maxW; i >= 1; i--) {
                for (int j = maxS; j >= 1; j--) {
                    if (w[x] <= i && s[x] <= j) {
                        sum[i][j] = Math.max(sum[i][j], v[x] + sum[i - w[x]][j - s[x]]);
                    }
                }
            }
        }
        System.out.println(" The greatest value of a backpack is " + sum[maxW][maxS]);
    }
}

Two dimensional cost knapsack variant

 

public class  Two dimensional cost knapsack variant  {
    public static void main(String[] args) {
        int[] O = {0, 3, 10, 5, 1, 4};// Oxygen content per cylinder 
        int[] N = {0, 36, 25, 50, 45, 20};// Nitrogen content per cylinder 
        int[] W = {0, 120, 129, 250, 130, 119};// Weight of each cylinder 
        int n = 5;// There are five types of cylinders 
        int needO = 5;// Oxygen needed 
        int needN = 60;// Nitrogen required 
        dp2(O, N, W, n, needO, needN);
    }

    public static void dp(int[] O, int[] N, int[] W, int n, int needO, int needN) {
        int[][] sum = new int[needO + 1][needN + 1];// It also needs to be i L oxygen and j L of nitrogen , Minimum total weight of cylinder 
        for (int x = 1; x < needO + 1; x++) {
            for (int y = 1; y < needN + 1; y++) {
                sum[x][y] = 0x3f3f3f3f;
            }
        }// initialization 
        for (int x = 1; x < n + 1; x++) {// Consider taking the 1 A cylinder , The first 2 A cylinder ,..., The first n A cylinder 
            for (int i = needO; i >= 0; i--) {// It is possible that the demand for oxygen is 0
                for (int j = needN; j >= 0; j--) {// It is possible that the demand for nitrogen is 0
                    if (O[x] >= i && N[x] >= j) {// If the current oxygen and nitrogen content , More than the oxygen and nitrogen needed 
                        sum[i][j] = Math.min(sum[i][j], W[x]);// If you don't take it, it is the weight of the cylinder in the last round , If you take it, it is the weight of the current cylinder 
                    } else if (O[x] < i && N[x] < j) {// If the current oxygen and nitrogen content , It is smaller than the oxygen and nitrogen needed 
                        sum[i][j] = Math.min(sum[i][j], W[x] + sum[i - O[x]][j - N[x]]);
                    } else if (O[x] >= i && N[x] < j) {// If the current oxygen content is greater than the demand , The nitrogen content is less than the demand 
                        sum[i][j] = Math.min(sum[i][j], W[x] + sum[i][j - N[x]]);// If I take , Oxygen has met the conditions , Only nitrogen is required to meet the conditions 
                    } else if (O[x] < i && N[x] >= j) {// If the current nitrogen content is greater than the demand , The oxygen content is less than the demand 
                        sum[i][j] = Math.min(sum[i][j], W[x] + sum[i - O[x]][j]);// If I take , Nitrogen has met the conditions , Only oxygen is needed to meet the conditions 
                    }
                }
            }
        }
        int min = sum[needO][needN];
        System.out.println(min);
    }


    public static void dp2(int[] O, int[] N, int[] W, int n, int needO, int needN) {
        int[][] sum = new int[needO + 1][needN + 1];// It also needs to be i L oxygen and j L of nitrogen , Minimum total weight of cylinder 
        for (int x = 1; x < needO + 1; x++) {
            for (int y = 1; y < needN + 1; y++) {
                sum[x][y] = 0x3f3f3f3f;
            }
        }// initialization 
        for (int x = 1; x < n + 1; x++) {// Consider taking the 1 A cylinder , The first 2 A cylinder ,..., The first n A cylinder 
            for (int i = needO; i >= 0; i--) {// It is possible that the demand for oxygen is 0
                for (int j = needN; j >= 0; j--) {// It is possible that the demand for nitrogen is 0
                    if (O[x] >= i && N[x] >= j) {// If the current oxygen and nitrogen content , More than the oxygen and nitrogen needed 
                        sum[i][j] = Math.min(sum[i][j], W[x]);// If you don't take it, it is the weight of the cylinder in the last round , If you take it, it is the weight of the current cylinder 
                    } else {
                        int k = i - O[x] >= 0 ? i - O[x] : i;
                        int m = j - N[x] >= 0 ? j - N[x] : j;
                        sum[i][j] = Math.min(sum[i][j], W[x] + sum[k][m]);
                    }
                }
            }
        }
        int min = sum[needO][needN];
        System.out.println(min);
    }
}