[01背包的搜索解法]+[1月13日总结]

tips:

  0.递归用来搜索;递归用来分治---(基于快速幂的思考,子问题的处理);递和归;快速幂的递归写法,快速幂的迭代写法。之前写的递归总结

  1.深度优先搜索:

    枚举所有完整路径以遍历所有情况的搜索方法(所有方案数,在根据条件排除一些方案---剪枝)---集合论的角度

  2.书中例子:走迷宫---“岔道口”、“死胡同”,“岔道口”---等到函数返回到这一层,再尝试其他岔路

  3.01背包搜索解法(联系1中路径的感觉,dfs函数参数的设计)

  4.剪枝:通过题目条件限制来节省dfs计算量的方法叫剪枝

  5.优先队列与排序中自定义排序规则的写法和区别。

[01背包的搜索解法]+[1月13日总结]
#include<iostream>

using namespace std;

const int maxn=1010;
int n,W,maxValue=0;
int w[maxn],v[maxn];
//题目中涉及了物品的重量和价值,因此也需要参数来记录在处理当前物品之前,
//已选物品的总重量sumW和总价值sumV
void dfs(int index, int sumW, int sumV){
    if(index==n){
        if(sumW<=W && sumV > maxValue){
            maxValue=sumV;
        }
        return;
    }
    dfs(index+1, sumW, sumV);
    //选第i间物品
    dfs(index+1,sumW+w[index],sumV+v[index]);
}

int main(){
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }

    dfs(0,0,0);
    cout<<maxValue<<endl;
    return 0;
}
01背包搜索解法 [01背包的搜索解法]+[1月13日总结]
#include<iostream>

using namespace std;

const int maxn=1010;
int n,W,maxValue=0;
int w[maxn],v[maxn];
void dfs(int index, int sumW, int sumV){
    if(index==n){
//        if(sumW<=W && sumV > maxValue){
//            maxValue=sumV;
//        }
        return;
    }
    dfs(index+1, sumW, sumV);
    //选第i件物品
    if(sumW+w[index]<= W){
        if(sumV+v[index]> maxValue){
            maxValue = sumV+v[index];
        }
        dfs(index+1,sumW+w[index],sumV+v[index]);
    }

}



int main(){
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }

    dfs(0,0,0);
    cout<<maxValue<<endl;
    return 0;
}
01背包递归优化版

sum:

  1.算法书要常读常新。

  2.看书中作者的表达看出思考问题的思路

上一篇:p126 跳跃游戏(leetcode 55)


下一篇:Python实现堆