题目地址
给 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;
- }
来源: https://www.cnblogs.com/zxcoder/p/12231720.html