完全背包（模板）
一、题目描述
描述
你有一个背包，最多能容纳的体积是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.
题目链接：
【模板】完全背包_牛客题霸_牛客网
二、 解题方法（动态规划）
先解决第一问：
1、状态表示
dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j ，所有的选法中，能挑选出来的最大价值。
2、状态转移方程
我们根据最后一步的状况，来分情况讨论。但是最后一个 物品能选很多个，因此我们的需要分很多情况：
（1） 选 0 个第 i 个物品 ：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j 。
此时 最大价值为 dp[i - 1][j] ；
（2） 选 1 个第 i 个物品 ：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j - v[i] 。因为挑选了一个 i 物品，此时 最大价值为 dp[i - 1][j - v[i]] + w[i]；
（3） 选 2 个第 i 个物品 ：此时相当于就是去前 i - 1 个物品中挑选，总体积不超过 j - 2 * v[i] 。因为挑选了两个 i 物品，此时 最大价值为 dp[i - 1][j - 2 * v[i]] + 2 * w[i] ；
（4）......
综上，我们的状态转移方程为：
dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]]+w[i], dp[i-1][j-2*v[i]]+2*w[i]...)
此时，可以进行优化，优化的方 向就是用一个或者两个状态来表示这一堆的状态，通常就是用数学的方式做一下等价替换。
我们发 现 第二维是有规律的变化的，因此我们去看看 dp[i][j - v[i]] 这个状态：
dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2*v[i]]+w[i],dp[i-1][j-3*v[i]]+2*w[i]...)
我们发现， 把 dp[i][j - v[i]] 加上 w[i] 正好和 dp[i][j] 中除了第一项以外的全部一致 ，因此我们可以修改我们的状态转移方程为：
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。
3、初始化
我们多加一行，方便我们的初始化，此时 仅需将第一行初始化为 0 即可 。因为什么也不选，也能
满足体积不大于 j 的情况，此时的价值为 0 。
4、填表顺序
根据状态转移方程， 仅需从上往下填表即可。
5、返回值
根据状态表示，返回 dp[n][V] 。
接下来解决第二问：
因为有可能凑不齐 j 体积的物品，因此我们把不合法的状态设置为 -1 。
1、状态表示
dp[i][j] 表示：从前 i 个物品中挑选，总体积正好等于 j ，所有的选法中，能挑选出来的最大价值。
2、状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]) 。
但是在使用 dp[i][j - v[i]] 的时候，不仅要判断 j >= v[i] ，又要判断 dp[i][j - v[i]] 表示的情况是否存在，也就是 dp[i][j - v[i]] != -1 。
3、初始化
我们多加一行，方便我们的初始化：
1） 第一个格子为 0 ，因为正好能凑齐体积为 0 的背包；
2） 但是第一行后面的格子都是 -1 ，因为没有物品，无法满足体积大于 0 的情况。
4、填表顺序
仅需从上往下填表即可。
5、返回值
由于最后可能凑不成体积为 V 的情况，因此返回之前需要判断一下。
三、代码
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);//输入n，Vint n = in.nextInt();int V = in.nextInt();//创建v,w数组，存每个物品的体积、价值int[] v = new int[n+1];int[] w = new int[n+1];//接下来输入n行，每行两个数vi和wifor (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，Vint n = in.nextInt();int V = in.nextInt();//创建v,w数组，存每个物品的体积、价值int[] v = new int[n+1];int[] w = new int[n+1];//接下来输入n行，每行两个数vi和wifor (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]);}
}