G≤15 时枚举饲料子集，按份数递增扫描，首个满足每种维生素总量均不低于需求的方案即最小解；子集总含量用最低位增量递推避免重复求和。
OJ: roj
题目 ID: 2024
难度:普及-
标签:枚举位运算记忆化USACO
创建: 2026-10-01 03:32
更新: 2026-10-06 09:46
题目描述
给定 V 种维生素的需求量，以及 G 种饲料各自的维生素含量。选出若干种饲料，使每种维生素的摄入总量都不低于需求，且所选饲料种数最少。输出最小种数 P 与按升序排列的饲料编号。
思路
G≤15，共有 2^G 个饲料子集。按子集内饲料种数 k 从 1 递增枚举，第一个满足条件的子集即为最优解。用最低位拆分递推计算每个子集对每种维生素的总含量，避免重复求和。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 03:32
# update_at: 2026-10-01 03:35
import sys
from functools import cache
def choice_is_ok(choice: int, amount: tuple[tuple[int, ...], ...], need: list[int]) -> bool:
"""方案是否可行：被选饲料对每种维生素的贡献之和都不低于需求量。
维生素按摄入总量计算，同一饲料的贡献可以累加，所以是逐种求和比较，
而不是取单份饲料的最大值。
"""
return all(subset_sum(choice, v, amount) >= need[v] for v in range(len(need)))
@cache
def subset_sum(choice: int, v: int, amount: tuple[tuple[int, ...], ...]) -> int:
"""方案 choice 在维生素 v 上的总含量：拆掉最低位那份饲料后递归累加。
低位编号是固定的划分依据——每个方案唯一定位到"最低位饲料 + 其余部分"，
于是 2^G 个方案的总含量只用各算一次，不必对每个方案重新扫全部饲料。
"""
if choice == 0:
return 0
low = choice & -choice # 最低位的 1，锁定一份必选饲料
g = low.bit_length() - 1
return amount[g][v] + subset_sum(choice ^ low, v, amount)
def best_choice(amount: tuple[tuple[int, ...], ...], need: list[int]) -> int:
"""返回可行方案中饲料份数最少的那个，用位集表示（饲料编号 i 对应第 i-1 位）。
按份数 k 严格递增扫描：份数更少的方案在更小的 k 上已经全部检查过，
所以第一个通过可行性检查的方案就是最优解，不需要再比较大小。
"""
full_choice = (1 << len(amount)) - 1 # 全选必然可行，兼作无解兜底
return next(
choice
for k in range(1, len(amount) + 1)
for choice in range(1, full_choice + 1)
if choice.bit_count() == k and choice_is_ok(choice, amount, need) # 位数 = 饲料份数
)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
V = next(data)
need = [next(data) for _ in range(V)] # 每天每种维生素的最小量
G = next(data)
# amount[g][v]：第 g+1 号饲料的维生素 v 含量；必须是元组，@cache 的键要可哈希
amount = tuple(tuple(next(data) for _ in range(V)) for _ in range(G))
chosen = best_choice(amount, need)
picks = [g + 1 for g in range(G) if chosen >> g & 1] # 编号从 1 开始，天然升序
print(f"{len(picks)} " + " ".join(map(str, picks)))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 09:46
* update_at: 2026-10-06 09:46
*/
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXV = 25;
const int MAXG = 15;
ll need[MAXV + 1]; // 每种维生素的需求量
ll a[MAXG + 1][MAXV + 1]; // a[i][j] 第 i 号饲料第 j 种维生素的含量
int n, m; // n 维生素种类数，m 饲料种数
// sum[s][j]：状态 s 里所有被选饲料的第 j 种维生素含量之和
ll sum[1 << MAXG][MAXV + 1];
// 返回状态 s 的二进制中 1 的个数，即所选饲料份数
int count_bit(int s) {
int cnt = 0;
while (s) {
cnt++;
s &= s - 1;
}
return cnt;
}
// 判断状态 s 是否可行：每种维生素的总量都不小于需求
bool ok(int s) {
for (int j = 1; j <= n; j++) {
if (sum[s][j] < need[j]) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> need[i];
cin >> m;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
int total = 1 << m;
// 按最低位拆分递推：sum[s] = sum[s 去掉最低位] + 最低位对应饲料的含量
for (int s = 1; s < total; s++) {
int low = s & -s; // 最低位的 1
int g = __builtin_ctz(low); // 最低位对应饲料编号 0..m-1
for (int j = 1; j <= n; j++) {
sum[s][j] = sum[s ^ low][j] + a[g + 1][j];
}
}
// 按份数 k 递增枚举，第一个可行的状态即最优解
for (int k = 1; k <= m; k++) {
for (int s = 1; s < total; s++) {
if (count_bit(s) != k) continue;
if (ok(s)) {
cout << k;
for (int i = 1; i <= m; i++) {
if (s & (1 << (i - 1))) cout << " " << i;
}
cout << "\n";
return 0;
}
}
}
return 0;
}