企事业网站建设/网页制作免费模板

题意：一共要吃n顿饭 公款m元

        如果公款大于等于饭局所需费用 就全用公款

        如果小于就自费

        求最后能用的公款为多少

思路：

        dfs(i - 1, val + dp[i]);

        dfs(i - 1, val);

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int dp[50];
int n, m;
int ans;void dfs(int i, int val)
{if(ans == m) return;if(val > m) return;if(i < 1){ans = max(ans, val);return;}int j, sum = val;for(j = i; j >= 1; j --)sum += dp[j];if(sum < ans) return;dfs(i - 1, val + dp[i]);dfs(i - 1, val);
}
int main()
{while(scanf("%d%d", &n, &m) != EOF){int i;for(i = 1; i <= n; i ++)scanf("%d", &dp[i]);sort(dp + 1, dp + 1 + n);ans = 0;dfs(n, 0);printf("%d\n", ans);}return 0;
}

转载于:https://www.cnblogs.com/sola1994/p/4430116.html