题解 | #【模板】完全背包#

package com.hhdd.dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定一个背包，能容纳体积为V。然后有n种物品，每种物品有一个对应的体积和价值。每种物品无限个
 * 求这个背包最多能装多大价值的物品。
 * 如果背包恰好装满，最多能装多大价值的物品。
 *
 * @Author HuangLusong
 * @Date 2022/4/5 13:35
 */
public class 完全背包 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        /**
         * 物品数量
         */
        int n = sc.nextInt();
        /**
         * 背包体积
         */
        int V = sc.nextInt();
        /**
         * 物品的体积数组
         */
        int[] v = new int[n + 1];
        /**
         * 物品的价值数组
         */
        int[] w = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        /**
         * dp1[i]表示体积为i下最大的价值
         */
        int[] dp1 = new int[V + 1];
        for (int i = 1; i <= V; i++) {

            for (int j = 1; j < v.length; j++) {
                if (v[j] > i) {
                    continue;
                }
                dp1[i] = Math.max(dp1[i - v[j]] + w[j], dp1[i]);
            }

        }
        System.out.println(dp1[V]);
        int[] dp2 = new int[V + 1];
        Arrays.fill(dp2, Integer.MIN_VALUE);
        dp2[0] = 0;
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j < v.length; j++) {
                if (v[j] > i) {
                    continue;
                }
                dp2[i] = Math.max(dp2[i - v[j]] + w[j], dp2[i]);
            }
        }
        if (dp2[V] < 0) {
            System.out.println(0);
        } else {
            System.out.println(dp2[V]);
        }
    }

    /**
     * 暴力递归解决下问题1：最大能装的价值，不要求恰好装满
     *
     * @param v
     * @param w
     * @param curV
     * @param num  标识用于解决问题1还是2
     * @return
     */
    public static int recursion(int[] v, int[] w, int curV, int num) {
        /**
         * 如果v中已经没有比curV还小的物品了，直接返回吧！
         */
        boolean flag = true;
        for (int i = 1; i < v.length; i++) {
            if (v[i] <= curV) {
                flag = false;
                break;
            }
        }
        if (flag) {
            /**
             * 如果是问题2，递归到最后还是无法将curV化成0，则表示装不满，不可达
             */
            if (num == 2) {
                if (curV == 0) {
                    return 0;
                } else {
                    return Integer.MIN_VALUE;
                }
            }
            return 0;
        }
        int res = 0;
        if (num == 2) {
            res = Integer.MIN_VALUE;
        }
        for (int i = 1; i < v.length; i++) {
            if (v[i] <= curV) {
                int temp = recursion(v, w, curV - v[i], num) + w[i];
                if (temp > res) {
                    res = temp;
                }
            }
        }
        return res;
    }


}