动态规划习题

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 数组如下：