DP习题
Melon的难题【01背包问题中“装满背包的最少物品数问题】
注意初始化问题，第一行除了第一个都要赋值最大值！！！
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int count = in.nextInt();
int[] arr = new int[count];
int sum = 0;
for (int i = 0; i < arr.length; i++) {
arr[i] = in.nextInt();
sum += arr[i];
}
if (sum % 2 != 0){
System.out.println(-1);
return;
}
int[][] dp = new int[count + 1][sum / 2 + 1]; // 装满背包所需最小物品数量
Arrays.fill(dp[0], count);
dp[0][0] = 0;
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j <= sum / 2; j++) {
if (j >= arr[i - 1]){
dp[i][j] = Math.min(dp[i - 1][j], dp[i -1][j - arr[i - 1]] + 1);
}else {
dp[i][j] = dp[i - 1][j];
}
}
}
//// 如果装满背包的最少物品数为n, 则说明没有平分方案，因为n个雨花石的重量之和为sumV，而背包的承重是bag = sumV / 2
if (dp[dp.length - 1][sum / 2] == count){
System.out.println(-1);
return;
}
System.out.println(dp[dp.length - 1][sum / 2]);
}
}
打印 DP 数组如下：
