HDOJ(HDU).2660 Accepted Necklace (DFS)
题意分析
给出一些石头，这些石头都有自身的价值和重量。现在要求从这些石头中选K个石头，求出重量不超过W的这些石头的最大价值是多少？
类似于之前讨论到的数字选不选的问题，此处面临的情况是石头选不选，若选进行一个dfs，若不选择进行另外一个dfs。考虑递归边界：
1.当选够了K个的时候，终止递归；
2.当当前重量大于W的时候，终止递归；
3.当所选石头的下标（代码中的pos）超过石头数量的时候，终止递归；
若遇到最优的情况，别忘记更新价值的最大值。
代码总览
/*
Title:HDOJ.2660
Author:pengwill
Date:2017-2-15
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define nmax 21
using namespace std;
int stone[nmax][2],n,m,val,ans,mwei;
void dfs(int num ,int nval,int nwei,int pos)
{
if(num==m)
if(nval>ans && nwei<=mwei ){ans = nval;return;}
else return;
if(nwei>mwei) return;
if(pos>n) return;
dfs(num+1,nval+stone[pos][0],nwei+stone[pos][1],pos+1);
dfs(num,nval,nwei,pos+1);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
ans = 0;
scanf("%d%d",&n,&m);
for(int i = 1; i<=n; ++i) scanf("%d%d",&stone[i][0],&stone[i][1]);
scanf("%d",&mwei);
dfs(0,0,0,1);
printf("%d\n",ans);
}
return 0;
}