讨论 / dfs过的,没有任何剪枝啊。谁能帮我算一下复杂度?
guanjun 2016-02-13 11:28:30
点我顶贴 收藏 删除
/* ***********************************************

Author :guanjun

Created Time :2016/2/13 10:22:28

File Name :1.cpp

************************************************ */

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <iomanip>

#include <list>

#include <deque>

#include <stack>

#define ull unsigned long long

#define ll long long

#define mod 90001

#define INF 0x3f3f3f3f

#define maxn 10000+10

#define cle(a) memset(a,0,sizeof(a))

const ull inf = 1LL << 61;

const double eps=1e-5;

using namespace std;

bool cmp(int a,int b){

return a>b;

}

int Max;

int a[1000];

int n,v;

void dfs(int i,int v,int sum){

if(i==n+1){

Max=max(sum,Max);return ;

}

if(v>=a[i]){

dfs(i+1,v,sum);

dfs(i+1,v-a[i],sum+a[i]);

}

else{

dfs(i+1,v,sum);

}

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("in.txt","r",stdin);

#endif

//freopen("out.txt","w",stdout);

int dp[100];

while(cin>>v>>n){

for(int i=1;i<=n;i++){

cin>>a[i];

}

cle(dp);

//dp[i][j]

Max=-1;

dfs(1,v,0);

cout<<v-Max<<endl;

}

return 0;

}

查看更多回复
提交回复