【算法】01背包问题分别用蛮力法，贪心，动态规划，回溯实现，分支限界法实现

一时失言乱红尘 2024-03-26 11:01 82阅读 0赞

## 实验内容： ##

给定n个重量为\{w1,w2,···,wn\}、价值为\{v1,v2,···,vn\}的物品和一个容量为C的背包，求能装入背包的的物品的最大价值

### 源程序及注释： ###

#include <bits/stdc++.h>
    using namespace std;
    struct item{
        
        int index;//序号
        int isput;//是否放入
        int w;//物品的重量
        int v;//物品的价值
        float per;//物品单位重量的价值
    }items[100];
    struct Node{
        
        int itemIdx;//节点所在的层级
        int cv;//当前价值
        int leftc;//剩余容量
        float bound;//优先级
        bool isleft;//是否时左节点
        Node *parent, *self;
        Node(){
        };
        Node(int _idx, int _cv, int _leftc, double _bound, bool _isleft, Node *_parent) {
        
            itemIdx = _idx;
            cv = _cv;
            leftc = _leftc;
            bound = _bound;
            isleft = _isleft;
            parent = _parent;
        }
        void selfptr(Node *ptr){
         
            self = ptr;
        }                                       
        //子节点需要记录当前节点为父节点，因此需要知道当前节点的地址
        friend bool operator<(const Node &a, const Node &b){
         return a.bound < b.bound; }
    };
    int n, c, bestValue = 0;
    int cx[100],cw = 0, cv = 0;
    /**
     * @brief 蛮力法
     * 
     * @return int 
     */
    int knapstack1(int i){
        
        if(i>n-1)
    	{
        
    		if(bestValue<cv&&cw<=c)
    		{
        
    			for (int k=0;k<n;k++){
        
                    items[k].isput = cx[k];
                    //cout << x[i]<<cx[i];
                }
                cout << endl;
    
                bestValue=cv;
                
            }
    		return bestValue;
    	}
    	cw=cw+items[i].w;
    	cv=cv+items[i].v;
    	cx[i]=1;
        
        knapstack1(i+1);
    	cw=cw-items[i].w;
    	cv=cv-items[i].v;
    	cx[i]=0;
    	knapstack1(i+1);
    	return bestValue;
    
    }
    /**
     * @brief 动态规划
     * 
     * @return int 
     */
    int knapstack2(){
        
        //dp[i][j]表示考虑1到i个物品时，当背包的容量为j时背包的最大价值
        int dp[n+1][c+1];
        int path[n + 1][c + 1];
        //初始化为0
        memset(dp,0,sizeof(dp));
        memset(path,0,sizeof(path));
        //初始化考虑第一个物品时
        for(int j=1;j<c+1;j++){
        
            if(j>items[0].w){
        
                dp[1][j]=items[0].v;
                path[1][j] = 1;
            }
        }
        //循环
        for(int i=2;i<n+1;i++){
        
            for(int j=1;j<c+1;j++){
        
                /**
                if(j>w[i-1]){
                    if(dp[i - 1][j - w[i - 1]] + v[i - 1]>dp[i - 1][j]){
                        dp[i][j] = dp[i - 1][j - w[i - 1]] + v[i - 1];
                    }else{
                        dp[i][j] = dp[i - 1][j];
                    }
                    
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
                */
               if(j>items[i-1].w&&dp[i - 1][j - items[i-1].w] + items[i-1].v>dp[i - 1][j]){
        
                   dp[i][j] = dp[i - 1][j - items[i-1].w] + items[i-1].v;
                   path[i][j] = 1;
               }else{
        
                   dp[i][j] = dp[i - 1][j];
               }
    
            }
        }
        //记录路径
        for (int i=n,j=c,k=n-1; i >=1 ,j>=1,k>=0; i--,k--)
        {
        
           if(path[i][j]){
        
               items[k].isput = 1;
               j -= items[k].w;
           }else{
        
               items[k].isput = 0;
           }
        }
        
        return dp[n][c];
        
    
    }
    /**
     * @brief 贪心法
     * 
     * @return int 
     */
    bool cmp(const item &a,const item &b){
        
        return a.per>b.per;
    }
    int knapstack3(){
        
        
        //求单位重量的价值
        for (int i = 0; i < n; i++)
        {
        
            items[i].per = items[i].v / items[i].w;
        }
        //根据单位重量的价值，从大到小排序
        sort(items, items + n, cmp);
        for (int i = 0; i < n; i++)
        {
        
            if(items[i].w<=c){
        
                c -= items[i].w;
                bestValue += items[i].v;
                items[i].isput = 1;
            }
        }
        return bestValue;
    }
    /**
     * @brief 回溯法
     * 
     * @return int 
     */
    int knapstack4(int i){
        
        if(i>n-1)
    	{
        
    		if(bestValue<cv)
    		{
        
    			for (int k=0;k<n;k++){
        
                    items[k].isput = cx[k];
                    //cout << x[i]<<cx[i];
                }
                bestValue=cv;
                
            }
    		return bestValue;
    	}
        if(cw+items[i].w<=c){
        
    	    cw=cw+items[i].w;
    	    cv=cv+items[i].v;
    	    cx[i]=1;
    
            knapstack4(i+1);
    	    cw=cw-items[i].w;
    	    cv=cv-items[i].v;
        }
    	cx[i]=0;
    	knapstack4(i+1);
    	return bestValue;
    
    }
    /**
     * @brief 分支限界法
     * 
     * @return int 
     */
    //上界函数
    float bound(int i,int cv,int cleft){
        
        float boundv = cv;
        while(i<n && cleft-items[i].w>=0){
        
            cleft -= items[i].w;
            boundv += items[i].v;
            i++;
        }
        if(i<n){
        
            boundv += cleft*items[i].per;
        }
        return boundv;
    
    
    }
    int knapstack5(){
        
        //求单位重量的价值
        for (int i = 0; i < n; i++)
        {
        
            items[i].per = items[i].v / items[i].w;
        }
        //根据单位重量的价值，从大到小排序
        sort(items, items + n, cmp);
        //优先队列
        priority_queue<Node> liveNodes;
        int i = 0;//节点所在层级
        int leftc = c;//剩余容量
        Node curNode, *parent = nullptr;
       
        //开始搜索解空间
        while(i<n){
        
            //左节点是否符合约束条件
            if(leftc>=items[i].w){
        
                if(cv+items[i].v>bestValue) bestValue = cv + items[i].v;        //更新最大价值
                Node *childNode = new Node(i+1, cv+items[i].v, leftc-items[i].w, bound(i+1, cv+items[i].v, leftc-items[i].w), true, parent);
                childNode->selfptr(childNode);
                liveNodes.push(*childNode);
            }
            //右节点检查上界条件
            int temp = bound(i+1, cv, leftc);
            if(temp>=bestValue){
        
                Node *childNode = new Node(i+1, cv, leftc, temp, false, parent);
                childNode->selfptr(childNode);
                liveNodes.push(*childNode);
            }
            //取下一节点
            curNode = liveNodes.top();
            liveNodes.pop();
            parent = curNode.self;
            leftc = curNode.leftc;
            cv = curNode.cv;
            i = curNode.itemIdx;
    
        }
    
        //记录路径
        Node *tempNode = &curNode;
        for (int i = n-1; i >=0 ; i--)
        {
        
            items[i].isput =tempNode->isleft;
            tempNode = tempNode->parent;
            
        }
        
    
        return bestValue;
    }
    int main() {
        
        //输入重量和价值，n表示有多少个物品，c表示背包的最大容量，w表示物品的重量，v表示物品的价值
        //x表示最终是否放入背包,cx表示临时是否放入背包
        cout << "请输入物品个数：";
        cin >> n ;
        cout << "请输入背包容量：";
        cin >> c ;
        cout << "请输入物品的重量和价值：" << endl;
    
        for (int i = 0; i < n; i++)
        {
        
            items[i].index = i;
            cin >> items[i].w >> items[i].v;
        }
        //蛮力法
        // cout <<"蛮力法，背包最大价值是："<< knapstack1(0) << endl;
        //动态规划法
        // cout <<"动态规划法，背包最大价值是："<< knapstack2() << endl;
        //贪心法
        // cout <<"贪心法，背包最大价值是："<< knapstack3() << endl;
        //回溯法
        // cout <<"回溯法，背包最大价值是："<< knapstack4(0) << endl;
        //分支限界法
        cout <<"分支限界法，背包最大价值是："<< knapstack5() << endl;
        cout << "物品的放入情况是" << endl;
        for (int i = 0; i < n; i++)
        {
        
            if(items[i].isput)
            cout << items[i].index << " ";
        }
        
        
    
        return 0;
    }