Accepted Necklace

1 
2 1 
1 1 
1 1 
3 

1 

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>

const int MAX = 21;

typedef struct Stone{
	int value;
	int weight;
}Stone;

Stone stone[MAX];
int visit[MAX];
int maxv,limit,k,n;

void dfs(int v,int w,int x,int cnt){
	if(w>limit || cnt>k)return;
	if(cnt==k){
		if(v>maxv){
			maxv=v;
		}
		return;
	}
	int i;
	//这个地方下标直接从x开始，因为宝石并没有要求序列问题只是求价值和，所以不需要考虑重复情况，是个很大的剪枝
	//举例： 3 4 5 6 == 4 3 5 6 == 5 3 6 4虽然序列不同，但是价值和相同，这样的只需要搜一次即可也就是前面搜过的重量不再搜
	for(i=x;i<n;++i){
		if(visit[i]==0){
			visit[i]=1;
			dfs(v+stone[i].value,w+stone[i].weight,i,cnt+1);
			visit[i]=0;
		}
	}
}


int main(){

	int t,i;
	//freopen("in.txt","r",stdin);
    scanf("%d",&t);
	while(t-- && scanf("%d %d",&n,&k)!=EOF){
		for(i=0;i<n;++i){
			scanf("%d %d",&stone[i].value,&stone[i].weight);
		}
		scanf("%d",&limit);
		maxv = INT_MIN;
		memset(visit,0,sizeof(visit));
		for(i=0;i<n;++i){
			visit[i]=1;
			dfs(stone[i].value,stone[i].weight,i,1);
			visit[i]=0;
		}
		printf("%d\n",maxv);
	}
    return 0;
}

HDU 2660 Accepted Necklace （DFS）,布布扣,bubuko.com

HDU 2660 Accepted Necklace （DFS）

原文：http://blog.csdn.net/iaccepted/article/details/23036963