DFS解01背包问题

01背包问题的DFS解法

直接dfs未剪枝代码

时间复杂度 O(2${}^n$),其原因是对任意的物品，都是选或者不选（两次的情况）

dfs三个形参
物品序号index，放进背包的重量sumW，以及放进背包的总价值sumC

主要搜索路径
序号为index的物品放入背包时
序号为index的物品不放入背包时

//搜索路径dfs(index+1,sumW+w[index],sumC+c[index]);//选第index件放入背包dfs(index+1,sumW,sumC);//不选第index件放入背包

代码

#include<iostream> using namespace std; const int maxn=100; int n,maxC=0,V,w[200],c[200];void dfs(int index,int sumW,int sumC ){//出口if(index==n){//遍历完所有 if(sumW<=V&&sumC>maxC)maxC=sumC;return ;} //搜索路径dfs(index+1,sumW+w[index],sumC+c[index]);//选第index件放入背包dfs(index+1,sumW,sumC);//不选第index件放入背包 } int main(){cin>>n>>V;//n件物品，V背包容量 for(int i=0;i<n;i++)cin>>w[i]>>c[i];//w重量，c价值dfs(0,0,0);//初始化index,sumW,sumC都为0 cout<<maxC<<endl;return 0;}

剪枝
选择第index件物品放入背包之前，先检查重量是否超过背包容量V，如果超过，便不进入dfs递归分支。
而且更新最大价值maxC也不需要无时无刻更新，只需要在当第index件物品放入背包后的价值超过放进背包之前的价值时更新。

#include<iostream> using namespace std; const int maxn=100; int n,maxC=0,V,w[200],c[200];void dfs(int index,int sumW,int sumC ){//出口if(index==n) return;//搜索路径dfs(index+1,sumW,sumC);//不选第index件物品放入背包 if(sumW+w[index]<=V){if(sumC+c[index]>maxC)maxC=sumC+c[index];dfs(index+1,sumW+w[index],sumC+c[index]);//选第index件物品放入背包} } int main(){cin>>n>>V;//n件物品，V背包容量 for(int i=0;i<n;i++)cin>>w[i]>>c[i];//w重量，c价值dfs(0,0,0);//初始化index,sumW,sumC都为0 cout<<maxC<<endl;return 0;}

对比剪枝前和剪枝后的代码，程序得以优化。

总结

以上是生活随笔为你收集整理的DFS解01背包问题的全部内容，希望文章能够帮你解决所遇到的问题。

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