完全背包问题

1.题目：

有 N种物品和一个容量是 V的背包，每种物品都有无限件可用。 第 i种物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

输入格式：

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。 接下来有 N 行，每行两个整数 vi,w 用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式：

输出一个整数，表示最大价值。

数据范围：

0 < N , V ≤ 1000

0 < vi , wi ≤ 1000

输入样例:

4 5

1 2

2 4

3 4

4 5

输出样例：

10

2.分析:

创建一个二维数组dp，其中dp[i][j]表示从前i个物品中选取一些放入容量为j的背包中能够得到的最大价值。 初始化dp数组的第一行，表示没有物品时，任何容量的背包价值都为0。

使用两层循环遍历所有物品和所有可能的背包容量。 对于每个物品i和每个容量j，考虑两种情况： 不取当前物品，即dp[i][j] = dp[i - 1][j]。 取当前物品，前提是当前物品的体积不大于背包容量，即dp[i][j] = max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1])。

这个算法的时间复杂度是O(NV)，空间复杂度也是O(NV). 该问题与“0 1背包问题”的主要区别在于物品的选择方式： 完全背包问题允许无限次选择每种物品，而01背包问题每种物品只能选择一次 所以，完全背包问题的状态转移为 dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]); 而0 1背包的状态转移为 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);

3.代码

import java.util.Scanner;
    public static class Main {
        public static void mian(String[] args){
            Scanner input = new Scanner(System.in);
            int N = input.nextInt();
            int V = input.nextInt();
            int []v = new int[N];
            int []w = new int[N];
            for(int i = 0;i<N;i++){
                v[i] = input.nextInt();
                w[i] = input.nextInt();
            }
            int dp[][] = new int[N+1][V+1];
            for (int i = 1; i <= N; i++) { 
                for (int j = 0; j <= V; j++) { 
                    dp[i][j] = dp[i - 1][j]; // 初始化
                    // 检查当前物品是否可以放入背包
                    if (v[i - 1] <= j) {
                        // 如果可以，考虑取当前物品的情况
                        // 计算不取当前物品时的价值和取当前物品的价值（即当前物品的价值加上剩余容量能达到的最大价值）中的较大值
                        dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i - 1]] + w[i - 1]);
                    }
                }
            }
            System.out.println(dp[N][V]);
        }
    }