zoj - 3631 - Watashis BG

題意：N天錢序列，最大報銷額為M，對於其中的一天可選擇報不不報，問最多能報銷多少錢。（每天的錢不可拆分）（1 <= N <= 30, 0 <= M <= 10000000）

——>>背包呀，不過要優化，寒假時優化到160ms，今天重刷，優化到了80ms，痛快！

優化思想：

1、從大到小排序；

2、到了最大報銷額，更新MAX；

3、將後面的加起來，看是否比現在的MAX小；

4、第3步中將後面的加起來，可事先打個前N項和的表。

[cpp] #include <cstdio>  
#include <algorithm>  
 
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 <cstdio>
#include <algorithm>

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 <cstdio>  
#include <algorithm>  
 
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; 
}