ACM-DFS之Accepted Necklace——hdu2660

#include <iostream>
#include <string.h>
using namespace std;
int max_wei,neck_num,n,va;
bool vis[21];

struct Stone
{
    int value,wei;
}sto[21];

// 注意，要将当前遍历到的位置向下传下去，否则会超时
void dfs(int js,int valu,int sum,int pre)
{
    if(js==neck_num)
    {
        va=valu>va?valu:va;
        return;
    }
    int i;
    for(i=pre;i<n;++i)
    {
        // 进行相应判断
        if(vis[i])  continue;
        if(sum+sto[i].wei<=max_wei)
        {
            vis[i]=1;
            dfs(js+1,valu+sto[i].value,sum+sto[i].wei,i);
            vis[i]=0;
        }
    }
}

int main()
{
    int i,total;
    cin>>total;
    while(total--)
    {
        // 输入相应数据
        cin>>n>>neck_num;
        for(i=0;i<n;++i)
            cin>>sto[i].value>>sto[i].wei;
        cin>>max_wei;
        memset(vis,0,sizeof(vis));

        va=0;
        dfs(0,0,0,0);
        cout<<va<<endl;

    }
    return 0;
}