Accepted Necklace/HDU 2660
题目
I have N precious stones, and plan to use K of them to make a necklace for my mother, but she won’t accept a necklace which is too heavy. Given the value and the weight of each precious stone, please help me find out the most valuable necklace my mother will accept.
Input
The first line of input is the number of cases.
For each case, the first line contains two integers N (N <= 20), the total number of stones, and K (K <= N), the exact number of stones to make a necklace.
Then N lines follow, each containing two integers: a (a<=1000), representing the value of each precious stone, and b (b<=1000), its weight.
The last line of each case contains an integer W, the maximum weight my mother will accept, W <= 1000.
Output
For each case, output the highest possible value of the necklace.
Sample Input
1
2 1
1 1
1 1
3
Sample Output
1
思路
题目大意是在所给出的石头中，找出能够组合出价值最大且重量不能大于W的组合的价值，第一个想到的是一个组合问题，又因为数据较小，所以可用递归去做。思想就是对于一块石头，取或不取。
代码
weight是判断重量是否大于W，value是价值总和，num是当前所取石头的个数，step是当前选择第几个石头
#include <cstdio>
#include <cstring>
int n,k,v[21],w[21],max,W;
void dfs(int weight,int value,int num,int step){if(weight>W) return;if(step==n&&num!=k) return;if(num==k){if(value>max) {max=value;}return;}dfs(weight+w[step],value+v[step],num+1,step+1);dfs(weight,value,num,step+1);
}
int main(){int t;scanf("%d",&t);while(t--){max=-1;//初始化scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d%d",&v[i],&w[i]);}scanf("%d",&W);dfs(0,0,0,0);printf("%d\n",max);}return 0;
}
题目链接