ZOJ--3631--Watashi's BG【枚舉】
來源：程序員人生 發(fā)布時間：2014-09-06 15:02:58 閱讀次數：2157次
鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4777
題意：有n天，告訴你每天的花費，別人給你一筆資金m，你自己也有一部分資金（可以假設花不完），每天只能花自己的錢或者花資金m中的錢，不能混著花，問m最多能花多少？
思路：考慮到數據比較小，n最多只有30，可以用枚舉來做，枚舉每天花m或者不花m，二進制枚舉，復雜度2^30。這樣復雜度要超時的，土豪說可以分兩部分枚舉，把結果存入兩個數組，然后這兩個數組結果再合并，復雜度n^2，這樣二進制枚舉最多是兩個2^15，大大縮短了時間復雜度。
后來我又用dfs寫了一遍，果斷T，看了別人的代碼，有個剪枝很關鍵，當前已使用的資金與所有還未使用的資金相加如果小于等于已得到的最大值，則剪枝。
二進制枚舉代碼
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 5000100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define MOD 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int a[200010],b[200010],va[40],vb[40];
int main(){
int i,j;
int n,m;
int la,lb,cnta,cntb,ans;
while(scanf("%d%d",&n,&m)!=EOF){
la = lb = cnta = cntb = ans = 0;
for(i=0;i<n/2;i++){
scanf("%d",&va[i]);
la++;
}
for(i=n/2;i<n;i++){
scanf("%d",&vb[i-n/2]);
lb++;
}
int l = (1<<la);
for(i=0;i<l;i++){
int sum = 0;
for(j=0;j<la;j++){
if(i&(1<<j)){
sum += va[j];
}
}
if(sum<=m){
a[cnta++] = sum;
ans = max(sum,ans);
}
}
l = (1<<lb);
for(i=0;i<l;i++){
int sum = 0;
for(j=0;j<lb;j++){
if(i&(1<<j)){
sum += vb[j];
}
}
if(sum<=m){
b[cntb++] = sum;
ans = max(sum,ans);
}
}
sort(a,a+cnta);
sort(b,b+cntb);
if(ans==m){
printf("%d
",ans);
continue;
}
for(i=cnta-1;i>=0;i--){
for(j=cntb-1;j>=0;j--){
if(a[i]+b[j]<=m){
ans = max(ans,a[i]+b[j]);
break;
}
}
}
printf("%d
",ans);
}
return 0;
}
DFS代碼
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 5000100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define MOD 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int a[40],jz[40];
int n,m,maxm;
void dfs(int step,int cnt){
if(cnt>m) return ;
maxm = max(maxm,cnt);
if(step<1) return ;
if(cnt+jz[step]<=maxm) return ; //防TLE剪枝
dfs(step-1,cnt);
dfs(step-1,cnt+a[step]);
}
int main(){
int i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
jz[0] = 0;
for(i=1;i<=n;i++) jz[i] = jz[i-1] + a[i];
maxm = 0;
dfs(n,0);
printf("%d
",maxm);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
