完全背包（模板）

一、题目描述

描述

你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为vi​ ,价值为wi​。

（1）求这个背包至多能装多大价值的物品？

（2）若背包恰好装满，求至多能装多大价值的物品？

输入描述：

第一行两个整数n和V，表示物品个数和背包体积。

接下来n行，每行两个数vi和wi，表示第i种物品的体积和价值。

1≤n,V≤10001≤n,V≤1000

输出描述：

输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

示例1

输入：

2 6
5 10
3 1

输出：

10
2

示例2

输入：

3 8
3 10
9 1
10 1

输出：

20
0

说明：

无法恰好装满背包。

示例3

输入：

6 13
13 189
17 360
19 870
14 184
6 298
16 242

输出：

596
189

说明：

可以装5号物品2个，达到最大价值298*2=596，若要求恰好装满，只能装1个1号物品，价值为189.

题目链接：

【模板】完全背包_牛客题霸_牛客网 

二、 解题方法（动态规划）

三、代码

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //输入n，V
        int n = in.nextInt();
        int V = in.nextInt();
        //创建v,w数组，存每个物品的体积、价值
        int[] v = new int[n+1];
        int[] w = new int[n+1];

        //接下来输入n行，每行两个数vi​和wi
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        //创建dp数组
        int[][] dp = new int[n + 1][V + 1];
        //初始化
        for (int j = 0; j <= V; j++) {
            dp[0][j] = 0;
        }
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= v[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
                }
            }
        }
        System.out.println(dp[n][V]);

        //将dp表清零，继续求解第二问
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = 0;
            }
        }

        //初始化dp表
        for (int j = 1; j <= V; j++) {
            dp[0][j] = -1;
        }
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= v[i] && dp[i][j-v[i]] != -1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
                }
            }
        }
        //要判断一下，是否存在能将背包装满的情况
         System.out.println(dp[n][V] == -1 ? 0 : dp[n][V]);
    }
}

四、空间优化

 代码：

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //输入n，V
        int n = in.nextInt();
        int V = in.nextInt();
        //创建v,w数组，存每个物品的体积、价值
        int[] v = new int[n+1];
        int[] w = new int[n+1];

        //接下来输入n行，每行两个数vi​和wi
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        //创建dp数组
        int[] dp = new int[V + 1];
        //初始化
        for (int j = 0; j <= V; j++) {
            dp[j] = 0;
        }
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= V; j++) {
                dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        System.out.println(dp[V]);

        //将dp表清零，继续求解第二问
        for (int j = 0; j <= V; j++) {
                dp[j] = 0;
        }

        //初始化dp表
        for (int j = 1; j <= V; j++) {
            dp[j] = -1;
        }
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = v[i]; j <= V; j++) {
                if (dp[j-v[i]] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
                }
            }
        }
         System.out.println(dp[V] == -1 ? 0 : dp[V]);
    }
}