01背包问题

参考视频https://www.bilibili.com/video/av36136952?from=search&seid=10516072371338376794

递归解法

import java.util.*;
public class problem {
    public int max(int a, int b) {
        if (a > b) {
            return a;
        } else
            return b;
    }
    public int B(int[][] a, int x, int k) {                                     // x代表前面还有x件东西可以拿，k表示还有k个空间可以存放东西
        if (x < 0) {                                                                      // 递归的出口
            return 0;
        } else if (k < a[x][1]) {                                                    // 递归的内部条件
            return B(a, x - 1, k);
        } else {
            return max(B(a, x - 1, k - a[x][1]) + a[x][0], B(a, x - 1, k));
        }
    }
    public static void main(String[] args) {
        problem p = new problem();
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();                                                 // 代表有几种商品可以拿0 1 2 3 4 5 6 7排列
        int m = input.nextInt();                                                // 代表背包可以装多少体积
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = input.nextInt();                                             // 价格
            a[i][1] = input.nextInt();                                             // 体积
        }
        n = n - 1;                                                                    // 使排列从0 1 2 3 4 5 6 7开始
        System.out.println(p.max(p.B(a, n - 1, m - a[n][1]) + a[n][0], p.B(a, n - 1, m)));
    }
}

非递归解法

import java.util.*;
public class problem {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();// 代表有几种商品可以拿 0 1 2 3 4 5 6 7排列
        int m = input.nextInt();// 代表背包可以装多少体积
        int[] v = new int[n];// 0到n-1
        int[] w = new int[n];// 从第0个商品开始 0到n-1
        // 下面为每个商品的价格
        for (int i = 0; i < n; i++) {
            v[i] = input.nextInt();// 0到n-1价格
        }
        // 下面为每个商品的体积
        for (int i = 0; i < n; i++) {
            w[i] = input.nextInt();// 0到n-1体积
        }
        // 背包问题非递归的话，要把所有结果放在一个二维数组中
        int[][] B = new int[n + 1][m + 1];// 空间能达到（0~n，0~m）
        // 二维数组的第0行以及第0列都为0;第一值开始的话为(1,1)
        int x, y;// x竖种类 y横体积
        for (x = 1; x < n + 1; x++) {
            for (y = 1; y < m + 1; y++) {
                if (w[x - 1] > y) {
                    B[x][y] = B[x - 1][y];
                } else {
                    int value1 = B[x - 1][y - w[x - 1]] + v[x - 1];
                    int value2 = B[x - 1][y];
                    if (value1 > value2) {
                        B[x][y] = value1;
                    } else
                        B[x][y] = value2;
                }
            }
        }
        System.out.println(B[n][m]);
    }
}