题意：N天钱序列，最大报销额为M，对于其中的一天可选择报不不报，问最多能报销多少钱。（每天的钱不可拆分）（1 <= N <= 30, 0 <= M <= 10000000）

?

——>>背包呀，不过要优化，寒假时优化到160ms，今天重刷，优化到了80ms，痛快！

优化思想：

1、从大到小排序；

2、到了最大报销额，更新MAX；

3、将后面的加起来，看是否比现在的MAX小；

4、第3步中将后面的加起来，可事先打个前N项和的表。

[cpp] #include ??
#include ??
?
using namespace std;?
?
const int maxn = 30 + 10;?
int N, M, MAX, a[maxn], sum[maxn];?
?
bool cmp(const int& e1, const int& e2)?
{?
??? return e1 > e2;?
}?
void dp(int cur, int cur_sum)?
{?
??? if(cur_sum == M)?
??? {?
??????? MAX = cur_sum;?
??????? return;?
??? }?
??? if(cur == N+1)?
??? {?
??????? MAX = max(MAX, cur_sum);?
??????? return;?
??? }?
??? if(cur_sum + sum[N] - sum[cur-1] < MAX) return;?
??? if(cur_sum + a[cur] <= M) dp(cur + 1, cur_sum + a[cur]);?
??? dp(cur + 1, cur_sum);?
}?
int main()?
{?
??? int i;?
??? while(scanf("%d%d", &N, &M) == 2)?
??? {?
??????? for(i = 1; i <= N; i++) scanf("%d", &a[i]);?
??????? sort(a + 1, a + 1 + N, cmp);?
??????? sum[0] = 0;?
??????? sum[1] = a[1];?
??????? for(i = 2; i <= N; i++) sum[i] = sum[i-1] + a[i];?
??????? MAX = 0;?
??????? dp(1, 0);?
??????? printf("%d\n", MAX);?
??? }?
??? return 0;?
}?

#include
#include

using namespace std;

const int maxn = 30 + 10;
int N, M, MAX, a[maxn], sum[maxn];

bool cmp(const int& e1, const int& e2)
{
??? return e1 > e2;
}
void dp(int cur, int cur_sum)
{
??? if(cur_sum == M)
??? {
??????? MAX = cur_sum;
??????? return;
??? }
??? if(cur == N+1)
??? {
??????? MAX = max(MAX, cur_sum);
??????? return;
??? }
??? if(cur_sum + sum[N] - sum[cur-1] < MAX) return;
??? if(cur_sum + a[cur] <= M) dp(cur + 1, cur_sum + a[cur]);
??? dp(cur + 1, cur_sum);
}
int main()
{
??? int i;
??? while(scanf("%d%d", &N, &M) == 2)
??? {
??????? for(i = 1; i <= N; i++) scanf("%d", &a[i]);
??????? sort(a + 1, a + 1 + N, cmp);
??????? sum[0] = 0;
??????? sum[1] = a[1];
??????? for(i = 2; i <= N; i++) sum[i] = sum[i-1] + a[i];
??????? MAX = 0;
??????? dp(1, 0);
??????? printf("%d\n", MAX);
??? }
??? return 0;
}

再次优化，0ms过！！！痛快！！！

优化思想5：

增加恰好到达M的标记。

[cpp] view plaincopyprint?#include ??
#include ??
?
using namespace std;?
?
const int maxn = 30 + 10;?
int N, M, MAX, a[maxn], sum[maxn];?
bool ok;?
?
bool cmp(const int& e1, const int& e2)?
{?
??? return e1 > e2;?
}?
void dp(int cur, int cur_sum)?
{?
??? if(ok) return;?
??? if(cur_sum == M)?
??? {?
??????? MAX = cur_sum;?
??????? ok = 1;?
??????? return;?
??? }?
??? if(cur == N+1)?
??? {?
??????? MAX = max(MAX, cur_sum);?
??????? return;?
??? }?
??? if(cur_sum + sum[N] - sum[cur-1] < MAX) return;?
??? if(cur_sum + a[cur] <= M) dp(cur + 1, cur_sum + a[cur]);?
??? dp(cur + 1, cur_sum);?
}?
int main()?
{?
??? int i;?
??? while(scanf("%d%d", &N, &M) == 2)?
??? {?
??????? for(i = 1; i <= N; i++) scanf("%d", &a[i]);?
??????? sort(a + 1, a + 1 + N, cmp);?
??????? sum[0] = 0;?
??????? sum[1] = a[1];?
??????? for(i = 2; i <= N; i++) sum[i] = sum[i-1] + a[i];?
??????? MAX = 0;?
??????? ok = 0;?
??????? dp(1, 0);?
??????? printf("%d\n", MAX);?
??? }?
??? return 0;?
}?