题目描述

01背包

JAVA 代码

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();
        }



        //自己理解：
        // v[i]： i的容积 , w[i]: i的权重
        // i 表示物品序号, j表示总容积
        //每一次将 包含 i 和 不包含i的集合 做一次比较.
        //结果存入前一层.
        //实在不理解把打印输出出来. 


        //f[0][?] 不含0集合,为空集. 所以从1开始.
        for(int i=1;i<=n; i++){
            for(int j=0; j<=m; j++){
                //不包含 i ==> 存在了上一层 相同j的位置.
                f[i][j] = f[i-1][j];
                //System.out.println("i="+ i + ", j ="+ j );
                //System.out.println("f[i][j] = " + f[i][j]);
                //总容积能够包含下 i 的容积
                if(j >= v[i]){
                    // f[i-1][j-v[i]] + w[i] 包含i 的集合. 
                    f[i][j] = Math.max(f[i][j], f[i-1][j-v[i]] + w[i]);
                    //System.out.println("f[i-1][j-v[i]] + w[i]= " + f[i-1][j-v[i]]+ "+" + w[i]);
                    //System.out.println("f[i][j]= " + f[i][j]);
                    //System.out.println();
                }
            }
            System.out.println();
        }
        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++){

            //1. 将 v[i]消除. j如果小于 v[i] 则不更新. 
            //2. 从大到小枚举. 可消除i-1上一层的影响. 
            // for(int j=0; j<=m;j++)
            for(int j=m; j>=v[i]; j--){

                //f[i][j] = f[i-1][j]; --> 被消除.
                // if(j >= v[i]){ --> 被消除
                    f[j] = Math.max(f[j],f[j-v[i]] + w[i]);

                // }
            }

        }
        System.out.println(f[m]);

    }
}