算法
(暴力枚举) $O(2^n \cdot n \cdot m)$
注意到每本算法书都有买和不买这两种选择,而 $N$ 最大只有 $12$,$M$ 最大只有 $12$,$2^{12} \times 12 \times 12 = 589824$
所以只需使用二进制枚举遍历 $2^{12} = 4096$ 种可能性即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
const int INF = 1001001001;
int a[12][12];
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
int n, m, x;
cin >> n >> m >> x;
vector<int> c(n);
rep(i, n) {
cin >> c[i];
rep(j, m) cin >> a[i][j];
}
int ans = INF;
rep(s, 1<<n) {
int cost = 0;
vector<int> d(m);
rep(i, n) {
if (s>>i&1) {
cost += c[i];
rep(j, m) d[j] += a[i][j];
}
}
bool ok = true;
rep(j, m) if (d[j] < x) ok = false;
if (ok) chmin(ans, cost);
}
if (ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}