背包问题

package pack;

import java.util.Arrays;

public class KnapSack {
    public static int getMax01(int[] b, int[] w, int total){
        int[][] mem = new int[b.length+1][total+1];
        for(int i=1;i<=b.length;i++){
            for(int j=1;j<=total;j++){
                mem[i][j] = mem[i-1][j];
                if(w[i-1]<=j) mem[i][j] = Math.max(mem[i][j], mem[i-1][j-w[i-1]]+b[i-1]);
            }
        }
        return mem[b.length][total];
    }
    public static int getMax01Optimize(int[] b, int[] w, int total){
        int[] mem = new int[total+1];
        for(int i=1;i<=b.length;i++){
            for(int j=total;j>=1;j--){
                mem[j] = mem[j];
                if(w[i-1]<=j)
                    mem[j] = Math.max(mem[j], mem[j-w[i-1]]+b[i-1]);
            }
            System.out.println(Arrays.toString(mem));
        }
        return mem[total];
    }public static void main(String[] args) {
//        System.out.println(getMax(new int[]{1,2,4,2,5},new int[]{1,2,3,2,5},10));
        System.out.println(getMax01Optimize(new int[]{1,2,4,2,5},new int[]{1,2,3,2,5},10));
        System.out.println(getMaxAllPackOptimize(new int[]{1,2,4,2,5},new int[]{1,2,3,2,5},10));
    }
}

package pack;

import java.util.Arrays;

public class KnapSack {

    public static int getMaxAllPack(int[] b, int[] w, int total){
        int[][] mem = new int[b.length+1][total+1];
        for(int i=1;i<=b.length;i++){
            for(int j=1;j<=total;j++){
                mem[i][j] = mem[i-1][j];
                if(w[i-1]<=j) mem[i][j] = Math.max(mem[i][j], mem[i][j-w[i-1]]+b[i-1]);
            }
        }
        return mem[b.length][total];
    }

    public static int getMaxAllPackOptimize(int[] b, int[] w, int total){
        int[] mem = new int[total+1];
        for(int i=1;i<=b.length;i++){
            for(int j=1;j<=total;j++){
                if(w[i-1]<=j) mem[j] = Math.max(mem[j], mem[j-w[i-1]]+b[i-1]);
            }
        }
        return mem[total];
    }

    public static void main(String[] args) {
        System.out.println(getMaxAllPackOptimize(new int[]{1,2,4,2,5},new int[]{1,2,3,2,5},10));
    }
}