之前网易笔试被血虐，后来仔细一想还是前段时间没刷题，没编程手感，前两题都是冷静点想想边界条件就能AC的。第三题一开始就是回溯法的思路，但是剪枝和非递归回溯法写半天没折腾出来。还是练少了没手感。
题目描述
动态规划
这是0-1背包问题的变种，0-1背包问题是每个物品有自己的价值，求最大价值。而这里相对简单，物品只有重量，没有价值，求所有放置种数。
简单明了的思路是动态规划
f(w, k) = f(w-v[k], k+1)+f(w, k+1)其中f(w, k)代表背包剩余容量w，从第k个包开始选择是否放入，一共有多少种方法。
看似需要建一个wn的大表，数量级10^930，内存肯定不够，但是可以用map来实现这个大表从而节省空间。
这里需要谨慎地处理初始值，w=0或k>=n时返回的是1，而w<0时返回的是0，而且此时无论k为何值，都返回1。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int n; LL w; vector<LL> v; // 输入数据
map<pair<LL, int>, LL> mp;
LL solve(LL cw, int k) {
if (cw < 0)
return 0;
if (k >= n || cw == 0)
return 1;
auto key = make_pair(cw, k);
if (mp.find(key) != mp.end()) {
return mp[key];
} else { // 表中没有这一项，需要在递归求解的同时加入表中
return mp[key] = solve(cw, k + 1) + solve(cw - v[k], k + 1);
}
}
int main() {
cin >> n >> w;
v.resize(n);
for (int i = 0; i < n; ++i)
cin >> v[i];
cout << solve(w, 0) << endl;
}
回溯法
之前公布示例答案时说回溯法不行，实际上是剪枝的姿势不对。先贴代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int n; LL w; vector<LL> v; // 输入数据
LL solve() {
LL cnt = (1 << n); // n<=30，int不会溢出
vector<int> x(n, 0); // x[i]=1代表放入第i个零食
int k = 0; // 决定当前是否放入第k袋零食
LL cw = 0; // 当前方案的零食总重量
while (k >= 0) {
if (cw + v[k] <= w) { // 加入当前零食
x[k] = 1; cw += v[k++];
} else { // 不能加入当前零食，且x[k]=1的所有可能都不存在
cnt -= (1 << (n - k - 1));
x[k] = 0;
}
if (k == n) { // 回溯，这里是关键
for (--k; k >= 0 && x[k] == 1; --k) {
cw -= v[k];
} // end: k < 0 or x[k] == 0
if (k < 0)
break;
for (; k >= 0 && x[k] == 0; --k) {
} // end: k < 0 or x[k] == 1
if (k < 0)
break;
x[k] = 0; cw -= v[k++];
}
}
return cnt;
}
int main() {
cin >> n >> w;
v.resize(n);
for (int i = 0; i < n; ++i)
cin >> v[i];
sort(v.begin(), v.end());
cout << solve() << endl;
}
注意每次while循环开始时必定满足条件：cw <= w且k<n。
当抵达叶子节点时，其实回溯两次，第一次回溯完毕后，x[k] == 0，代表加入了该节点，但是之后的节点均加入了，所以该节点的右子树无需遍历，因为右子树的解对应的cw肯定是小于左子树最左边的节点的cw。
