特殊要求

(1) 输出字典序最小的最优方案

这里“字典序最小”的意思是1 ～N 号物品的选择方案排列出来以后字典序最小。

一般而言，求一个字典序最小的最优方案，只需要在转移时注意策略：以0/1背包为例。在某一阶段，两种决策的结果相同，就应该按照前者来输出方案。

(2) 求方案总数

以0/1背包为例。它的状态转移方程为 f[i][c]＝maxíìîff[[ii－－1][1][cc]－w[i]]＋v[i]

除了可以求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。

只需把状态转移方程中的max改成sum（求和），并将初始条件设为 f[0][0]=1，就可以通过 f[n-1][C] 求出方案总数。

事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。

(3) 最优方案的总数

这里的最优方案是指物品总价值最大的方案。以01背包为例。

结合求最大总价值和方案总数两个问题的思路，最优方案的总数可以这样求：开一个数组 g[i][c]，表示这个子问题的最优方案的总数。在求 f[i][c]的同时，顺便就把 g[i][c]带下来了。

代码如下：

for (int i=1;i<=n;i++)  for (int c=0;c<=C;c++) {   f[c]=f[i-1][c];   if (c>=w) f[c] = max(f[c], f[i-1][c-w] + v);   g[c]=0;    if (f[c]==f[i-1][c])    g[c] += g[i-1][c];   if (f[c] == (f[i-1][c-w] + v))    g[c] += g[i-1][c-w] + v;   // 注：如果两个状态的值相等，那么计算g时应该把两部分都算进去。这就是必须单独求g的原因。 }

(4) 求次优解、第K优解

对于求次优解、第 K 优解类的问题，如果相应的最优解问题能写出状态转移方程、用动态规划解决，那么求次优解往往可以相同的复杂度解决，第 K 优解则比求最优解的复杂度上多一个系数 K。

其基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。

以0/1背包为例。0/1背包的状态转移方程为 f[i][c]＝maxíìîff[[ii－－1][1][cc]－w[i]]＋v[i] ②①。如果要求第

K优解，那么状态 f[i][c]就应该是一个大小为 K 的数组 f[i][c][K＋1]。其中 f[i][c][k]表示前 i 个物品、背包大小为 c 时，第 k 优解的值。显然可以认为 f[i][c][K＋1]是一个有序队列。

然后可以说：f[i][c]这个有序队列是由①、②这两个有序队列合并得到的。有序队列①即 f[i－1][c][K]，

②则理解为在 f[i－1][c－w][K]的每个数上加上 v[i]后得到的有序队列。合并这两个有序队列并将结果的前 K 项储存到 f[i][c][K＋1]中的复杂度是O(K)。最后的答案是f[N][C][K]。总的复杂度是O(CNK)。

实际上，一个正确的状态转移方程的求解过程已经覆盖了问题的所有方案。只不过由于是求最优解，所以其它达不到最优的方案都被忽略了。因此，上面的做法是正确的。

另外，要注意题目对于“第 K 优解”的定义，将策略不同但权值相同的两个方案是看作同一个解还是不同的解。如果是前者，则维护有序队列时要保证队列里的数没有重复的。