1.简述：
描述
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为
,价值为
。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数
和
，表示第i种物品的体积和价值。
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出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.
2.代码实现：
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// 以下代码用于获取输入数据
Scanner scan = new Scanner(System.in);
String nV = scan.nextLine(); // 获取物品个数和背包体积
int n = Integer.valueOf(nV.split(" ")[0]); // 获取背包个数
int V = Integer.valueOf(nV.split(" ")[1]); // 获取背包体积
int[] v = new int[n + 1]; // 定义一个整型数组，用于存放物品的体积
int[] w = new int[n + 1]; // 定义一个整型数组，用于存放物品的重量
String vw;
for (int i = 1; i <= n; i++) {
vw = scan.nextLine();
v[i] = Integer.valueOf(vw.split(" ")[0]); // 第 i 种物品的体积
w[i] = Integer.valueOf(vw.split(" ")[1]); // 第 i 种物品的重量
}
// 以下代码是完全背包问题的具体实现
// 为了提高效率，1）求这个背包至多能装多大价值的物品 2）若背包恰好装满，求至多能装多大价值的物品
// 以上两个问题同时进行求解，并且我们直接使用数组压缩的方式，而不再使用朴素算法
// 事实上，问题一和问题二的区别仅仅是数组 dp 初始化的不同而已
int[] dp1 = new int[V + 1];
int[] dp2 = new int[V + 1];
// 注意，dp2 用于存放的是第二问的状态表示，初始化时，所有 dp[i] 都置为 Integer.MIN_VALUE
Arrays.fill(dp2, Integer.MIN_VALUE);
dp2[0] = 0; // 注意，当体积为 0 时，是合法的状态
for (int i = 1; i <= n; i++) {
for (int j = v[i]; j <= V; j++) { // 完全背包问题和01背包问题，在代码层面上的区别就是这一层循环的方向不一样
dp1[j] = Math.max(dp1[j], dp1[j - v[i]] + w[i]);
dp2[j] = Math.max(dp2[j], dp2[j - v[i]] + w[i]);
if (dp2[j] < 0) {
// 如果 dp2[i] 小于 0，我们可以认为此时的 dp 不合法，即不能使背包恰好装满
dp2[j] = Integer.MIN_VALUE;
}
}
}
System.out.println(dp1[V]);
System.out.println(dp2[V] == Integer.MIN_VALUE ? 0 : dp2[V]); // 别忘了判断当前 dp 是否合法
return;
}
}