题目描述

01背包问题

算法1

(dfs+剪枝)

时间复杂度 最差为$O(n*n^2)$

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Goods{
    int no;
    int w;
    int v;
    Goods(int no,int w,int v){
        this->no=no;
        this->w=w;
        this->v=v;
    }
    bool operator<(const Goods&s) const{
        return (double)v/w>(double)s.v/s.w;
    }
};
vector<Goods>g;
int W;
int n;
vector<int>x;
vector<int>bestx;
int bestv=0;
int tot=0;
double bound(int cw,int cv,int i){
    int rw = W-cw;
    double b = cv;
    int j = i;
    while(j < n&&g[j].w <=rw){
        rw -= g[j].w;
        b += g[j].v;
        j++;
    }
    if(j<n){
        b+=(double)g[j].v/g[j].w*rw;
    }
    return b;
}
void dfs(int cw,int cv,int i){
    if(i >= n){
        if(cw <= W && cv > bestv){
            bestv = cv;
            bestx = x;
        }
    }
    else{
        if(g[i].w+cw <=W){
            x[i] = 1;
            dfs(cw+g[i].w,cv+g[i].v,i+1);
        }
        double b = bound(cw,cv,i+1);
        //cout << "当前i是"<<i<<"  "<<"当前b是"<<b<<endl; 
        if(b > bestv){
            x[i] = 0;
            dfs(cw,cv,i+1);
        }
    }
}
int main(){
    cin>>n>>W;
    int tmp1,tmp2;
    for(int i = 0;i < n;i++){
        cin>>tmp1>>tmp2;
        g.push_back(Goods(i,tmp1,tmp2));
    }
    sort(g.begin(),g.end());
    x = vector<int>(n,0);
    dfs(0,0,0);
    cout << bestv<<endl;
}