# 背包问题求情况数
这里讨论的求情况数的方法适用于任意的背包问题, 题目仅供参考.
## 题目
### 题目描述
买奖品: 小明有20元钱, 有N件奖品可供购买, 每件可购买无数件. 求在剩余钱最少时, 可供选择的购买方案数.
输入n, 接下来n件奖品的单价. 输出要求的结果.
### 样例输入
```text
2 5 10
```
### 样例输出
```text
3
```
## 题目分析
如果问题转变为求最少剩余钱数(最多花费钱数), 很显然就是一道有关费用的完全背包问题. 转移方程为:
$$
dp[i][j] = \begin{cases}
0, &i = 0 \vee j = 0 \\
dp[i-1][j], &j < cost[i] \\
max(dp[i-1][j], dp[i][j-cost[i]] + cost[i]), &其他
\end{cases}
$$
求情况数即是在这样的完全背包���路之上做了一点小的拓展和包装.
我们将$cnt[i][j]$定义为在拥有$j$元钱, 遍历到第$i$项物品时, 能达到最优解的情况个数. 之后, 这里用到了由dp结果逆推dp过程的技巧(类似LCS求子序列内容):
- 若$dp[i][j]$是仅由$dp[i-1][j]$得来的, 那么二者本身就是一种情况
- 若$dp[i][j]$是仅由$dp[i][j-cost[i]] + cost[i]$计算得来的, 那么视二者为相同情况(因为具有直接继承关系).
- 若$dp[i][j]$是可以由$dp[i-1][j]$和$dp[i][j-cost[i]] + cost[i]$同时推出来的, 那么$dp[i][j]$一定聚合了其余两种情况.
根据上述分析, 得出状态转移方程:
$$
cnt[i][j] = \begin{cases}
1, &i = 0 \vee j = 0 \\
cnt[i-1][j], &(dp[i][j] = dp[i-1][j]) \wedge (dp[i][j] \ne dp[i][j-cost[i]] + cost[i]) \\
cnt[i][j-cost[i]], &(dp[i][j] \ne dp[i-1][j]) \wedge (dp[i][j] = dp[i][j-cost[i]] + cost[i]) \\
cnt[i-1][j] + cnt[i][j-cost[i]], &(dp[i][j] = dp[i-1][j]) \wedge (dp[i][j] = dp[i][j-cost[i]] + cost[i]) \\
\end{cases}
$$
为了方便, cnt的初值设定为1. 在存在最优解(情况数$\ge$1)时, 这样没有任何问题; 但如果不存在最优解(即背包问题失效)时, 应当返回其他标志(如0或-1). 因此此处需要特别判断.
## 代码(C++)
此处带有滚动数组优化.
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n + 1);
for (int i = 1; i <= n; ++i)
cin >> v[i];
// 完全背包
vector<int> dp1(25, 0), dp2(25, 1);
for (int i = 1; i <= n; ++i) {
for (int j = v[i]; j <= 20; ++j) {
int lastdp = dp1[j-v[i]] + v[i];
if (lastdp > dp1[j]) {
dp1[j] = lastdp;
dp2[j] = dp2[j-v[i]];
} else if (lastdp == dp1[j]) {
dp2[j] += dp2[j-v[i]];
}
}
}
if (dp1[20])
cout << dp2[20] << endl;
else
cout << 0 << endl;
return 0;
}
```
![]()