你要购买 种物品各一件，一共有 家商店，你到第 家商店的路费为 ，在第 家商店购买第 种物品的费用为 ，求最小总费用。
链接
题解
将所有的物品压进一个二进制集合中，用 表示已经尝试了前 个商店，已购买物品集合为 的最小总费用。
使用类似背包的方式枚举每个物品转移即可。
代码
#include <cstdio>
#include <cassert>
#include <queue>
#include <utility>
const int maxn = 100;
const int maxm = 16;
const int maxstatus = 1 << 16;
int main() {
int n, m;
scanf("%d %d", &n, &m);
static int c[maxn][maxm], d[maxn];
for (int i = 0; i < n; i++) {
scanf("%d", &d[i]);
for (int j = 0; j < m; j++) scanf("%d", &c[i][j]);
}
static int f[maxn][maxstatus];
for (int j = 0; j < (1 << m); j++) {
f[0][j] = d[0];
for (int k = 0; k < m; k++) {
if (j & (1 << k)) f[0][j] += c[0][k];
}
}
f[0][0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < (1 << m); j++) f[i][j] = f[i - 1][j] + d[i];
for (int j = 0; j < (1 << m); j++) {
for (int k = 0; k < m; k++) {
if (j & (1 << k)) f[i][j] = std::min(f[i][j], f[i][j ^ (1 << k)] + c[i][k]);
}
}
for (int j = 0; j < (1 << m); j++) f[i][j] = std::min(f[i][j], f[i - 1][j]); // , printf("f[%d][%d] = %d\n", i, j, f[i][j]);
}
printf("%d\n", f[n - 1][(1 << m) - 1]);
return 0;
}