题目描述

完全背包问题

JAVA 代码

朴素算法
时间复杂 最坏 O(n^2 * m);

import java.util.*;
import java.io.*;

class Main{
    static int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] f =new int[N][N];

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        for(int i = 1; i<= n;i++){
            v[i] = sc.nextInt();
            w[i] =sc.nextInt();
        }

        for(int i=1; i<=n;i++){
            for(int j = 0;j<=m; j++){
                for(int k=0; k* v[i]<=j; k++){

                    //朴素算法 
                    f[i][j] = Math.max(f[i-1][j-v[i]*k] + w[i]*k, f[i][j]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

优化

import java.util.*;
import java.io.*;

class Main{
    static int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[][] f =new int[N][N];

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        for(int i = 1; i<= n;i++){
            v[i] = sc.nextInt();
            w[i] =sc.nextInt();
        }

        for(int i=1; i<=n;i++){
            for(int j = 0;j<=m; j++){


                //朴素算法 
                // f[i][j] = Math.max(f[i-1][j-v[i]*k] + w[i]*k, f[i][j]);
                f[i][j] = f[i-1][j];
                if(j>= v[i]){
                    /**公式为：
                    * f[i][j] = 
                    * {f[i-1][j-v[i]*1] + w[i]*1 ,
                    *  f[i-1][j-v[i]*2] + w[i]*2 ,
                    *  ...
                    *  f[i-1][j-v[i]*k] + w[i]*k ,
                    * }
                    * 
                    * f[i][j-v] = 
                    * {f[i-1][j-v[i]*1] + w[i]*0 ,
                    * f[i-1][j-v[i]*2] + w[i]*1 ,
                    * f[i-1][j-v[i]*k] + w[i]*k-1 ,
                    * }
                    * 
                    * 由此可得 
                    * f[i][j] 与 f[i][j-v] 只多个w[i]
                    * 那max 也是只多个 w[i];
                    */          
                    f[i][j] = Math.max(f[i][j], f[i][j-v[i]] + w[i]);
                }
            }
        }
        System.out.println(f[n][m]);
    }
}

维度优化

import java.util.*;
import java.io.*;

class Main{
    static int N = 1010;
    static int[] v = new int[N], w = new int[N];
    static int[] f =new int[N];

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        for(int i = 1; i<= n;i++){
            v[i] = sc.nextInt();
            w[i] =sc.nextInt();
        }

        for(int i=1; i<=n;i++){
            for(int j = v[i];j<=m; j++){
                f[j] = Math.max(f[j], f[j-v[i]] + w[i]);
            }
        }
        System.out.println(f[m]);
    }
}