【算法】01背包问题

有n个重量和价值分别为wi，vi的物品。 从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

限制条件

1<= n <=100

1<=wi，vi<=100

1<=W<=10000

代码：

import java.util.Scanner;

public class Main {
    static int n,W;
    static int w[],v[];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        W = in.nextInt();
        w = new int[n];
        v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        System.out.println(rec(0, W));

    }
    public static int rec(int i,int j){
        int res;
        if (i == n){
            res = 0;
        }else if (j < w[i]){
            res = rec(i+1, j);
        }else{
            res  = Math.max(rec(i+1, j),rec(i+1,j-w[i])+v[i] );
        }
        return  res;
    }
}

上面的代码会出现重复计算的问题，我们可以对其再进行优化，从而节省时间。

import java.util.Scanner;

public class Main {
    static int N,W;	//背包数量，目标重量
    static int w[],v[]; //重量，价值
    static int dp[][];	//记忆数组
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        W = in.nextInt();
        w = new int[N];
        v = new int[N];
        dp = new int[N+1][W+1];
        for (int i = 0; i < N; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        //对记忆数组初始化
        for (int i = 0; i <=N; i++) {
            for (int j = 0; j <=W; j++) {
                dp[i][j] = -1;
            }
        }
        System.out.println(rec(0, W));
    }
    public static int rec(int i,int j){
        //当记忆数组中有值，直接返回
        if (dp[i][j]>=0){
            return dp[i][j];
        }
        int res;
        if (i == N){
            res = 0;
        }else if (j < w[i]){
            res = rec(i+1, j);
        }else{
            res  = Math.max(rec(i+1, j), rec(i+1,j-w[i]) +v[i] );
        }
        //节点的值储存在记忆数组中
        return dp[i][j] = res;
    }
}

终极优化

import java.util.Scanner;

public class Main {
    static int N, W;
    static int w[], v[];
    static int dp[][];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        W = in.nextInt();
        w = new int[N];
        v = new int[N];
        dp = new int[N + 1][W + 1];
        for (int i = 0; i < N; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        System.out.println(rec());
    }

    public static int rec() {
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j <= W; j++) {
                if (j < w[i]) {
                    dp[i][j] = dp[i + 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
                }
            }
        }
        return dp[0][W];
    }
}