HDU-2660 Accepted Necklace

GDUT 2020寒假训练 专题一 D

原题链接

• HDU-2660 Accepted Necklace
• GDUT-专题1-D BFS/DFS

题目大意

有N个石头想要从中选出K个做成项链，每颗石头有自己的价值和重量，求选择的K颗石头总重不超过W的最大价值

思路1

深搜
深搜K层，若当前的石头可以用且当前总重+选择这颗石头的重量不超过W，那么就往下搜，并且将当前石头的状态置为不可用，搜到K个后，将当前的价值，与历史最高价值进行比较更新，最后输出历史最高价值。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<memory.h> using namespace std; bool check[25]; int v[25],w[25]; int maxxv,k,n,W; void dfs(int step,int num,int weight,int value) {if(num==k){maxxv=max(maxxv,value);}for(int i=step;i<=n;i++){if(check[i]&&weight+w[i]<=W){check[i]=false;dfs(i+1,num+1,weight+w[i],value+v[i]);check[i]=true;}}return ; } int main() {int T;cin>>T;while(T--){cin>>n>>k;memset(check,true,sizeof check);maxxv=0;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}cin>>W;dfs(1,0,0,0);cout<<maxxv<<endl;}//尝试背包、枚举、宽搜 应该都可以 return 0; }

思路2

感觉直接枚举也可以

思路3

这道题其实读完题感觉可以用二维背包来做，但是背包写的还不熟练，先用深搜试了一下 二维背包的坑再填

总结

以上是生活随笔为你收集整理的HDU-2660 Accepted Necklace的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。