P5194 [USACO05DEC] Scales S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路参考 大佬 薛定谔的鱼 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
维护一个前缀和数组 从后往前一个个遍历所有可能的组合
然后进行一定的剪枝
void bfs(int now,ll ma){
if(ma>m){
return ;//不符合条件返回 #减枝1
}
if(ma+b[now]<=ans){
return ;//如果往前所有砝码全选上都小于当前最优答案 那么返回 #减枝2
}
ans=max(ans,ma); //走到这已经符合条件 先判断更新一下答案
for(int i=now;i;i--){
bfs(i-1,ma+a[i]);//对于当前 now这个编号的砝码遍历其所有可能的组合
}
}
遍历递归 的逻辑图
我们会一个个往前搜 搜完所有可能的组合
完整代码
#include<iostream>
using namespace std;
typedef long long ll;
ll ans;
int n,m;
ll a[1010],b[1010];
void bfs(int now,ll ma){
if(ma>m){
return ;//不符合条件返回 #减枝1
}
if(ma+b[now]<=ans){
return ;//如果往前所有砝码全选上都小于当前最优答案 那么返回 #减枝2
}
ans=max(ans,ma); //走到这已经符合条件 先判断更新一下答案
for(int i=now;i;i--){
bfs(i-1,ma+a[i]);//对于当前 now这个编号的砝码遍历其所有可能的组合
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=b[i-1]+a[i];
}
bfs(n,0);
cout<<ans;
return 0;
}
