# 307-13-14-子集枚举DP

## P3959 宝藏

### 题目描述

$L$代表这条道路的长度，$K$代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

### 输出格式

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1


4

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2  

5

【样例解释1】

【样例解释2】

【数据规模与约定】

### 题解

$$f(lv,S) = \min_{T\subset S} \Big \{ f(lv - 1,S-T) + lv \times \sum_{u\in T}\min_{a\in S-T}w(u, a)\Big \}$$

$$L'\times K = w(u,P_9) \times lv > w(u,P_9)\times (lv' + 1)$$

$$f_{i\in V} (0,\{i\}) = 0,~f_{S \subset V,~|S| ≥2}(0,S) = \infty$$

$$f(i,S) = \begin {cases} ~0~~~~~~~i\in V,S=\{i\} \\ \infty~~~~~~\text{otherwise} \end {cases}$$

\begin {align*} S=(&~11000111~)_2 \\ &\downarrow\downarrow\downarrow\downarrow\downarrow\downarrow\downarrow\downarrow \\ &~87654321 \end {align*}

1. 要判断$T$是否为$S$的子集，只需要判断：

$(S~|~T)==S$即可。

2. 如果要判断$e$是否在集合$S$当中，只需要判断

$(S ~|~(1~\text{<<}~e)) == S$即可。

3. 想要求$S-T$这个集合：

$S-T=S~\text{^}~T$。

4. 迭代递归求子集：

$T = (T-1) ~\&~ S$，其中$T$为子集$S$为全集，$T$的初始值为$S$，这样可以枚举$S$的所有子集，时间复杂度为$O(3^n)$而不是$O(4^n)$。

#include <iostream>
#define inf 1e9;
using namespace std;

typedef long long ll;

ll n, m, w[13][(1 << 12) + 5], f[13][(1 << 12) + 5];

int main() {
cin >> n >> m;
if (n == 1 && m == 0) {
cout << 0 << endl;
return 0;
}
for (ll i = 0; i < 13; i ++)
for (ll s = 0; s < (1 << n); s ++)
w[i][s] = inf;
while (m --> 0) {
ll u, v, len; cin >> u >> v >> len;
u --; v --;
w[u][1 << v] = min(w[u][1 << v], len);
w[v][1 << u] = min(w[v][1 << u], len);
}
for (ll i = 0; i < n; i ++)
for (ll s = 1; s < (1 << n); s ++) {
ll lb = s & (-s);
w[i][s] = min(w[i][s - lb], w[i][lb]);
}
for (ll i = 0; i < n; i ++) {
for (ll s = 0; s < (1 << n); s ++)
f[i][s] = inf;
}
for (ll j = 0; j < n; j ++)
f[0][1 << j] = 0;
for (ll lv = 1; lv < n; lv ++) {
for (ll s = 0; s < (1 << n); s ++) {
for (ll t = s - 1; t > 0; t = (t - 1) & s) {
ll sum = 0;
for (ll x = 0; x < n; x ++)
if ((t | (1 << x)) == t) sum += w[x][s ^ t];
f[lv][s] = min(f[lv][s], f[lv - 1][s ^ t] + lv * sum);
}
}
}
ll ans = inf;
for (ll i = 1; i < n; i ++)
ans = min(ans, f[i][(1 << n) - 1]);
cout << ans << endl;
return 0;
}

## P3052 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper

### 题目描述

A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don't like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than W.

## 输入输出格式

* Line 1: N and W separated by a space.

* Lines 2..1+N: Line i+1 contains the integer C_i, giving the weight of one of the cows.

* A single integer, R, indicating the minimum number of elevator rides needed.

one of the R trips down the elevator.

### 输入输出样例

4 10
5
6
3
7


3

## 说明

There are four cows weighing 5, 6, 3, and 7 pounds. The elevator has a maximum weight capacity of 10 pounds.

We can put the cow weighing 3 on the same elevator as any other cow but the other three cows are too heavy to be combined. For the solution above, elevator ride 1 involves cow #1 and #3, elevator ride 2 involves cow #2, and elevator ride 3 involves cow #4. Several other solutions are possible for this input.

### 题解

$$\left [\begin {matrix} f(S) \\ g(S) \end {matrix}\right ] = \min_{u\in S} \begin {cases} \left [\begin {matrix} f(\complement _S\{u\}) \\g(\complement_S\{u\}) +w(u) \end {matrix}\right ] & g(\complement_S\{u\}) + w(u) ≤C \\ \left [\begin {matrix} f(\complement_S\{u\}) + 1 \\ w(u) \end {matrix}\right ] & \text{otherwise} \end {cases}$$

$$\left [\begin {matrix} f(S) \\g(S) \end {matrix}\right ]$$

AC代码：

#include <iostream>
#include <algorithm>

using namespace std;
pair<int, int> f[1 << 23];
int n, c, w[1 << 23];

int main() {
cin >> n >> c;
int all = (1 << n) - 1;
for (int i = 0; i < n; i ++)
cin >> w[i];
for (int s = 1; s <= all; s ++) {
f[s] = make_pair(n, 0);
for (int u = 0; u < n; u ++) {
if (s & (1 << u)) {
int x = f[s ^ (1 << u)].first;
int y = f[s ^ (1 << u)].second;
if (y + w[u] <= c) {
f[s] = min(f[s], make_pair(x, y + w[u]));
} else {
f[s] = min(f[s], make_pair(x + 1, w[u]));
}
}
}
}
cout << f[all].first + (f[all].second ? 1 : 0) << endl;
return 0;
}