启发式搜索(直观命名+详细注释版)

代码参考至oiwiki

题目:

https://www.luogu.com.cn/problem/P1048dda

#include<bits/stdc++.h>
using namespace std;int n,m,ans;struct Node{int time,value;   //耗时与价值double cost_performance;    //性价比
} node[102];bool cmp(Node p,Node q){return p.cost_performance>q.cost_performance; //排序,性价比高的优先
}int still(int num,int package){    //估值函数 //计算在取了num个、剩余时间package的情况下,还能取到的剩余物品的最大价值int tot = 0;    //统计价值for(int i=1;num+i<=n;i++){if(package>=node[i+num].time){    //如果剩余时间package>=node[i+num]的耗时package -= node[num+i].time;tot+=node[num+i].value;}else return (int)(tot+package*node[num+i].cost_performance);   //若剩余时间package<node[i+num]的耗时,则 tot+剩余时间*node[i+num]的性价比 作为估算的最大值}return tot;  //若剩余时间能取完剩余所有就返回tot
}void dfs(int num,int package,int value){   //dfs搜索ans = max(ans,value);if(num>n) return;  //边界条件判出if(still(num,package)+value>ans) dfs(num+1,package,value);  //若还能取的剩余物品的估计最大值<=ans,则剪枝不搜了if(node[num].time<=package) dfs(num+1,package-node[num].time,value+node[num].value);    //若剩余时间package<node[num]的耗时,则剪枝不搜了
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>m>>n;for(int i=1;i<=n;i++){cin>>node[i].time>>node[i].value;node[i].cost_performance = 1.0 * node[i].value / node[i].time;    //计算第i个物品的性价比}sort(node+1,node+1+n,cmp);dfs(1,m,0);cout<<ans;return 0;
}