题意：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;
}