牛客在线编程_牛牛的背包问题
Keane1998 人气:2题目地址
给n个物品的体积和背包的总容量,问能装下的方案数。
- 搜索+剪枝,当剩余容量小于后缀最小值时直接返回1,即全不选,当剩余容量大于后缀和时直接返回1<<len。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=32;
int n;
ll w,v[N],mn[N],suf[N];
ll dfs(int idx,ll rem){
if(rem<mn[idx]){
return 1;
}
if(rem>=suf[idx]){
return 1ll<<n-idx+1;
}
if(idx==n){
if(rem>=v[idx]){
return 2;
}else{
return 1;
}
}
ll ans=0;
if(rem>=v[idx]){
ans+=dfs(idx+1,rem-v[idx]);
}
ans+=dfs(idx+1,rem);
return ans;
}
int main(){
scanf("%d%lld",&n,&w);
for(int i=1;i<=n;i++){
scanf("%lld",&v[i]);
}
mn[n+1]=0x3f3f3f3f;
for(int i=n;i>=1;i--){
mn[i]=min(mn[i+1],v[i]);
suf[i]=suf[i+1]+v[i];
}
ll ans=dfs(1,w);
printf("%lld\n",ans);
return 0;
}
加载全部内容