思路

1. 关键还是找准状态表示，刚开始尝试求“方案数”，结果为0的就是无法凑出。一顿操作猛如虎，发现二维状态得到的方案数不考虑使用到的邮票个数。再多加一维表示“已选邮票的个数”，时间复杂度$O(N\*K_{max}\*({W_{max}}\*K_{max}))$原地爆炸。一翻题解，好家伙，方向整个就偏了，求的应该是“凑成某个面额使用到的邮票数目最小值”，当最小值大于$K$时，该面额无法凑成
2. 邮票种数$N$为物品数量，输入的邮票面额为物品价值，背包容量应为能凑出的最大数$K_{max}\*W_{max}=2\*10^6$，时间复杂度$O(N\*K_{max}\*W_{max}) = O(10^8)$
3. $f(i,j)$表示“只考虑前$i$个邮票且组成面额恰好为$j$的选法集合”，属性：所需邮票数目$Min$
4. 状态计算
   • 不选：$f(i,j) = f(i-1, j)$
   • 选：$f(i,j) = f(i, j-v) + 1$ 【$f(i, j-v)$是完全背包优化后的式子，$+1$是选了当前邮票故总个数增加】
   • 综上：$f(i,j) = min(f(i-1,j), f(i, j-v)+1)$
5. 初始化边界条件，
   • 求最小，所以所有状态先初始化到一个极大值（注意如果使用最大值，因为有$+1$，会导致$f(i, j-v)+1$结果为负数）
   • $f(0,0) = 0$ 表示“不使用任何邮票且总面额恰好为0时，所需邮票的最小数目为0（什么都不用）”，【更准确的做法是$f(i,0)=0$？不太确定，烦请指正，感觉主要跟$j$的循环起点有关系】
6. 使用二维的状态表示则空间复杂度为$O(10^8)$，需要优化到一维，优化后的状态计算为$f(j) = min(f(j), f(j-v)+1)$，循环顺序无需改变依然从$0$到$K_{max}\*W_{max}$

代码

import java.lang.*;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, m, k;
    static int[] f = new int[2000010];

    public static void main(String[] args) {
        k = scanner.nextInt();
        n = scanner.nextInt();
        m = 200 * 10000;  // 计算能凑出的最大数
        Arrays.fill(f, k + 10000);  // 赋一个极大值
        f[0] = 0;  // 初始化边界条件
        for (int i = 1; i <= n; i++) {
            int v = scanner.nextInt();
            for (int j = v; j <= m; j++) {
                f[j] = Math.min(f[j], f[j - v] + 1);
            }
        }
        // 从1开始顺序遍历 找第一个所需邮票数大于K的位置 其前一位就是所求答案
        for (int i = 1; i <= m; i++) {
            if (f[i] > k) {  // “能凑出来但超过限制”的值为K+x  “不能凑出来”的值为初始极大值
                System.out.println(i - 1);
                return;
            }
        }
    }
}