pku 3400 搜索 wa.txt

来自「ACM资料大集合」· 文本 代码 · 共 62 行

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3400 搜索 WA
#define NMAX 12
#define INFI 99999
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

bool used[NMAX];
int w[NMAX];
int v[NMAX];
int num,d;
int ans;
void dfs(int now,int w1,int w2,int value,int count)
{
	int i;
	used[now]=true;
	if(count==num && ans<value) ans=value; 
	for(i=1;i<=num;i++)
	{
		if(false==used[i])
		{
			if(w1+d<=w2+w[i]) dfs(i,w1+w[i],w2,value,count+1);//必须放在w1
		   	else if(w1+w[i]>=w2+d) dfs(i,w1,w2+w[i],value+v[i],count+1);//必须放在w2
			else
			{
				dfs(i,w1+w[i],w2,value,count+1);
				dfs(i,w1,w2+w[i],value+v[i],count+1);
			}
			used[i]=false;	
		}
	}	
}

void solve()
{
	int i;
	ans=0;
	for(i=1;i<=num;i++) 
		dfs(i,w[i],0,0,1);
	printf("%d\n",ans);
}

int main()
{
	int i;
	scanf("%d %d",&num,&d);
	for(i=1;i<=num;i++) scanf("%d %d",&w[i],&v[i]);
	solve();
	return 0;
}