这道题如果用 DFS 必须剪枝:剪掉重复的组合。DFS 枚举了所有的排列,实际上这道题只需要组合。
View Code
# include <cstdio> # include <cstring> # define N 20 + 5 int ans; int n, k, vMax, v[N], w[N]; bool vis[N]; void dfs(int cur, int sum, int cnt, int weight) { if (weight > vMax) return ; if (cnt == k) ans = (sum > ans ? sum : ans); else { for (int i = cur+1; i <= n; ++i) if (vis[i] == false) { vis[i] = true; dfs(i, sum+v[i], cnt+1, weight+w[i]); vis[i] = false; } } } void init(void) { scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) scanf("%d%d", &v[i], &w[i]); scanf("%d", &vMax); memset(vis, false, sizeof(vis)); } void solve(void) { ans = 0; dfs(0, 0, 0, 0); printf("%d\n", ans); } int main() { int T; scanf("%d", &T); while (T--) { init(); solve(); } return 0; }
/**/