0-1背包C++回溯法实现

【实例简介】0-1背包C 回溯法实现

4 5
1 2
2 4
3 4
4 5

【实例截图】

【核心代码】

/*
    0-1背包：回溯法    
 */
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
const int N = 1e5 1e3;
struct Node{
    int weight , value ;
    double valPerWei;
}num[N];
int n , maxWeight, bestv;
bool vis[N];
vector<int> vec;

bool cmp(Node a , Node b ){
    return a.valPerWei>b.valPerWei;
}
double calc(int bgindex , int resi){
    //  开始的下标    剩余重量
    int i , j ;
    double res = 0;
    for(i = bgindex ; i <= n ; i ){
        if(resi >= num[i].weight){
            res = num[i].value;
            resi -= num[i].weight;
        }else{
            res = resi * num[i].valPerWei;
            break;
        }
    }
    return res;
}
void dfs(int index , int sum , int resi , double bn){
        //下标 现在的value和  剩余可用重量  从这以后最多可以的value
    if(index > n){
        if(sum > bestv){
            bestv = sum;
            vec.clear();
            for(int i = 1 ; i <= n ; i ){
                if(vis[i]){
                    vec.push_back(i);
                }
            }
        }
        return ;
    }else{
        if(double(bestv) >= double(sum) bn){
            return ;
        }
        if(resi >= num[index].weight){
            sum = num[index].value;vis[index] = true;
            dfs(index 1 , sum , resi-num[index].weight , bn);
            sum -= num[index].value;vis[index] = false;
        }
        bn = calc(index 1 , resi);
        if(double(bestv) >= double(sum) bn){
            return ;
        }
        dfs(index 1 , sum , resi , bn);
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int i , j ;
    double bn;
    cin>>n>>maxWeight;
    for(i = 1 ; i <= n ; i ){
        cin>>num[i].weight>>num[i].value;
        num[i].valPerWei = 1.0*num[i].value/num[i].weight;
    }
    sort(num 1 , num 1 n , cmp);
    cout<<"--------以下为输出结果****"<<endl;
    bn = calc( 1 , maxWeight);
    dfs(1 , 0 , maxWeight , bn);
    cout<<bestv<<endl;
    cout<<endl;
    return 0;
}