【题解】洛谷P2725 [USACO3.1]邮票 Stamps

从n种邮票中选出不超过k张邮票，使选出来的邮票可以表示1~m之间（含）的所有数。

每张邮票在不超过k的前提下，都可以使用无数次，因此可以将问题看成一个完全背包问题。
n种邮票就是n种物品，邮票面值就是体积，价值就是选出邮票的数量。问题转化为在n个物品里选出体积恰好为m且总价值最小的完全背包问题。

最后我们从1~m枚举一遍f[i], f[i]<=k的i都是邮票能表示出来的面值。时间复杂度为O(n * M), n是邮票种数，M是各种面值的邮票的总和。

顺便谈谈体积恰好是j的初始化问题：
朴素的状态转移方程为f[i][j] = max(f[i - 1][j], f[i][j - v] + w)（体积至多为j，所有元素初始化为0)。
体积恰好为j的情况下，f[0][0] (下标从1开始)表示从前0个物品中选，体积恰好为0，所以这个状态是合法的。但是f[0][1~j]都是不合法的，因为不可能一件物品都不选反而能凭空出现j的体积，所以这些状态都是不合法的，根据题目求最大/最小值，可以分别将这些状态初始为-INF/INF。
而体积至多为j的情况下，f[0][0] 和 f[0][1~j] 都是合法的，他们都初始化为0。

在以上基础上，再用滚动数组优化，就有了下面的代码。

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int M = 2000010;
 6 
 7 int n, k;
 8 int f[M];
 9 
10 int main() {
11     cin >> k >> n;
12     memset(f, 0x3f, sizeof f);
13     f[0] = 0;
14     for(int i = 0; i < n; i++) {
15         int v;
16         cin >> v;
17         for(int j = v; j <= M; j++) {
18             f[j] = min(f[j], f[j - v] + 1);
19         }
20     }
21     int res = 0;
22     for(int i = 1; i <= M; i++) {
23         if(f[i] > k) {
24             cout << res << endl;
25             return 0;
26         }
27         else res++;
28     }
29     return 0;
30 }