(模板)深度优先遍历与背包问题

向右看齐 2022-03-25 15:52 137阅读 0赞

深度优先算法除了可以解决图遍历问题,还可以解决背包问题,主要思想是遇到岔路:选还是不选

比如背包问题:

![20190121165406104.png][]

对于每件物品都有选或者不选两种情况,好比迷宫中的岔路,这时候我们可以利用深度优先算法思想遍历出所有的情况,然后选择不超过V的同时物品价值最大的情况

void DFS(int index, int sumW, int sumC) {
    	//递归到界限的话,退出循环
    	if (index == n) {
    		if (sumW + w[index] <= V && sumC + c[index] > maxValue) {   //剪枝部分
    		      maxValue = sumC + c[index];
              }
              return;
    	   }
    	   DFS(index+1, sumW, sumC); 
    	   DFS(index + 1, sumW + w[index], sumC + c[index]); 
    	}
    }

这样的话我们把所有的情况遍历了一遍,时间复杂度为O(2^n)

我们可以继续优化,只有在当前重量<V时才进入岔道,这样可以省去部分没有用的道路,降低时间复杂度

const int MAXN = 30;
    int n, V, maxValue = 0;
    int w[MAXN], c[MAXN];
    
    void DFS(int index, int sumW, int sumC) {
    	//递归到界限的话,退出循环
    	if (index == n) {
    		return;
    	}
    	DFS(index+1, sumW, sumC); //先选择不选
    	if (sumW + w[index] <= V) {   //剪枝部分
    		if (sumC + c[index] > maxValue) {
    			//更新最大质量
    			maxValue = sumC + c[index];
    		}
    		DFS(index + 1, sumW + w[index], sumC + c[index]);  //选
    	}

另外一种背包问题的题型也可以用深度优先算法解决

### 给定N个整数(有可能有负数),从中选择K个数,使得这K个数之和恰好等于一个给定的整数X,如果有多种方案,选择它们中元素平方和最大的那一种 ###

对于每一个数,有选或者不选两种方案,即两条岔路

我们可以定义一个vector,执行选方案时,将选的数push入vector,然后判断是否达到条件

如果没有达到条件,则将这个数弹出vector,然后执行不选的方案

int n,k,x,maxSumSqu = -1,A[maxn];
    vector<int> temp,ans;
    void DFS(int index, int nowK, int sum, int sumSqu){
        if(nowK == k && sum == x){
           if(sumSqu > maxSumSqu){
               maxSumSqu = sumSqu;
               ans = temp;
           }
           return;
        }
    
        if(index == n || nowK > k || sum > x) return;
         
        temp.push_back(A[index]);
        DFS(index+1, nowK+1, sum+A[index], sumSqu+A[index]*A[index]);
        temp.pop_back();
        DFS(index+1, nowK, sum, sumSqu);
    }

如果同一个数可以被重复选择的话,只需把

DFS(index+1, nowK+1, sum+A[index], sumSqu+A[index]*A[index]);

改成

DFS(index, nowK+1, sum+A[index], sumSqu+A[index]*A[index]);

具体问题:[https://blog.csdn.net/alex1997222/article/details/86580252][https_blog.csdn.net_alex1997222_article_details_86580252]

[20190121165406104.png]: /images/20220325/aa25a7f451df468ca75d0dde118b6670.png
[https_blog.csdn.net_alex1997222_article_details_86580252]: https://blog.csdn.net/alex1997222/article/details/86580252