【模板】完全背包

普通解法

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int capacity;//背包容量
    static int count;//物品个数
    static int [] v;//物品体积
    static int [] w;//物品价值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        count = in.nextInt();
        capacity = in.nextInt();
        v = new int[count+1];
        w = new int[count+1];
        //读取物品体积和价值，从1开始
        for(int i = 1;i <= count;i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        //背包不装满情况
        int ret1 = notFilled();
        //背包装满情况
        int ret2 = filled();
        //打印结果
        System.out.println(ret1);
        System.out.println(ret2);
    }

    private static int notFilled(){
        //初始化dp表，dp[i][j]表示从前i个物品中的所有选法中体积不超过j的最大价值
        int [][] dp = new int[count+1][capacity+1];
        //我们无需初始化，因为对于边界情况，比如第一列，我们填表的时候会进行特殊判断
        //同时对于第一行，没有选择物品最大价值肯定是0嘛
        //——————————————状态转移方程推导———————————————————
        //如果我们不选当前i物品，那我们直接dp[i-1][j]
        //如果我们选择一个i物品，则为dp[i-1][j-v[i]]+w[i]
        //如果我们选择两个i物品，则为dp[i-1][j-2v[i]]+2w[i]
        //.........
        //如果我们选择k个i物品（不超过背包容量），则为dp[i-1][j-kv[i]]+kw[i]
        //—————————————————————————————————————————————————
        //如果我们进行等价替换，把dp[i][j]中j-->j-v[i]，则方程变为
        //dp[i-1][j-v[i]]  dp[i-1][j-2v[i]]+w[i] ......... dp[i-1][j-kv[i]]+(k-1)w[i]
        //发现没有，我们如果进行等价替换，dp[i][j-v[i]]就包括了dp[i][j]从dp[i][j-v[i]]+w[i]开始后面的值
        //并且只相差一个w[i]，我们直接加上就好了
        //因此我们最终的状态转移方程是Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i])
        for(int i = 1;i <= count;i++){
            for(int j = 0;j <= capacity;j++){
                dp[i][j] = dp[i-1][j];
                //判断背包剩余空间是否符合要求
                if(j >= v[i]){
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                }
            }
        }
        return dp[count][capacity];
    }

    private static int filled(){
        int [][] dp = new int[count+1][capacity+1];
        //初始化，对于第一列我们不用管，因为我们填表会进行判断
        //但是对于第一行，第一个位置是0，因为我们没有选物品体积为0就是0
        //但是从下一个开始，我们为了区分究竟是不存在状态还是初始化状态
        //-1表示这个状态不存在，0就表示默认
        for(int i = 1;i <= capacity;i++){
            dp[0][i] = -1;
        }
        for(int i = 1;i <= count;i++){
            for(int j = 0;j <= capacity;j++){
                dp[i][j] = dp[i-1][j];
                if(j >= v[i] && dp[i][j-v[i]] != -1){
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);
                }
            }
        }
        return dp[count][capacity] == -1 ? 0 : dp[count][capacity];
    }
}

---

我们可以做空间优化，常数级别的时间复杂度优化

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int capacity;//背包容量
    static int count;//物品个数
    static int [] v;//物品体积
    static int [] w;//物品价值
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        count = in.nextInt();
        capacity = in.nextInt();
        v = new int[count+1];
        w = new int[count+1];
        //读取物品体积和价值，从1开始
        for(int i = 1;i <= count;i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        //背包不装满情况
        int ret1 = notFilled();
        //背包装满情况
        int ret2 = filled();
        //打印结果
        System.out.println(ret1);
        System.out.println(ret2);
    }

    private static int notFilled(){
        //初始化dp表，dp[i][j]表示从前i个物品中的所有选法中体积不超过j的最大价值
        //空间优化一：一维数组
        int [] dp = new int[capacity+1];
        //我们无需初始化，因为对于边界情况，比如第一列，我们填表的时候会进行特殊判断
        //同时对于第一行，没有选择物品最大价值肯定是0嘛
        //——————————————状态转移方程推导———————————————————
        //如果我们不选当前i物品，那我们直接dp[i-1][j]
        //如果我们选择一个i物品，则为dp[i-1][j-v[i]]+w[i]
        //如果我们选择两个i物品，则为dp[i-1][j-2v[i]]+2w[i]
        //.........
        //如果我们选择k个i物品（不超过背包容量），则为dp[i-1][j-kv[i]]+kw[i]
        //—————————————————————————————————————————————————
        //如果我们进行等价替换，把dp[i][j]中j-->j-v[i]，则方程变为
        //dp[i-1][j-v[i]]  dp[i-1][j-2v[i]]+w[i] ......... dp[i-1][j-kv[i]]+(k-1)w[i]
        //发现没有，我们如果进行等价替换，dp[i][j-v[i]]就包括了dp[i][j]从dp[i][j-v[i]]+w[i]开始后面的值
        //并且只相差一个w[i]，我们直接加上就好了
        //因此我们最终的状态转移方程是Math.max(dp[i-1][j],dp[i][j-v[i]]+w[i])
        for(int i = 1;i <= count;i++){
            //常数时间优化：从左向右填表，并且不从0开始填表
            for(int j = v[i];j <= capacity;j++){
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        return dp[capacity];
    }

    private static int filled(){
        int [] dp = new int[capacity+1];
        //初始化，对于第一列我们不用管，因为我们填表会进行判断
        //但是对于第一行，第一个位置是0，因为我们没有选物品体积为0就是0
        //但是从下一个开始，我们为了区分究竟是不存在状态还是初始化状态
        //-1表示这个状态不存在，0就表示默认
        for(int i = 1;i <= capacity;i++){
            //常数时间优化：配合填表形成无限小的数
            dp[i] = -0x3f3f3f3f;
        }
        for(int i = 1;i <= count;i++){
            for(int j = v[i];j <= capacity;j++){
                //为什么可以简化if判断？因为如果dp[j-v[i]]+w[i]结果足够小，比-1还小，最终结果还是dp[j]
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        return dp[capacity] < 0 ? 0 : dp[capacity];
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int num = in.nextInt();
        int bagW = in.nextInt();
    
        int[] array = new int[bagW+1];
        int[] array1 = new int[bagW+1];
        for(int j=bagW;j>0;j--){
                array1[j]=Integer.MIN_VALUE;
        }
        for(int i=1;i<=num;i++){
            int w = in.nextInt();
            int v = in.nextInt();
            for(int j=bagW;j>=0;j--){
                int max = array[j];
                int max1 = array1[j];
                for(int k=1;k*w<=j;k++){
                    max=Math.max(array[j-k*w]+k*v,array[j]);
                    max1=Math.max(array1[j-k*w]+k*v,array1[j]);
                }
                array[j]=max;
                array1[j]=max1;
            }
        }
        System.out.println(array[bagW]);
        if(array1[bagW]<0){
            array1[bagW]=0;
        }
        System.out.println(array1[bagW]);
    }
}