精华内容
下载资源
问答
  • 分支限界法解决01背包问题

    千次阅读 2021-02-13 02:34:33
    1. 问题描述设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i(1<= i <... 队列式分支限界法可以通过画分支限界法状态空间树的搜索图来理解具体思想和流程每一层按顺序...

    1. 问题描述

    设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i(1<= i <=n)装入背包,则有价值为pi . 目标是找到一个方案, 使得能放入背包的物体总价值最高.

    设N=3, W=(16,15,15),   P=(45,25,25), C=30(背包容量)

    2. 队列式分支限界法

    可以通过画分支限界法状态空间树的搜索图来理解具体思想和流程

    每一层按顺序对应一个物品放入背包(1)还是不放入背包(0)

    4f4bfd25c6acd41aceb89709707ea3bf.png

    步骤:

    ① 用一个队列存储活结点表,初始为空

    ② A为当前扩展结点,其儿子结点B和C均为可行结点,将其按从左到右顺序加入活结点队列,并舍弃A。

    ③ 按FIFO原则,下一扩展结点为B,其儿子结点D不可行,舍弃;E可行,加入。舍弃B

    ④ C为当前扩展结点,儿子结点F、G均为可行结点,加入活结点表,舍弃C

    ⑤ 扩展结点E的儿子结点J不可行而舍弃;K为可行的叶结点,是问题的一个可行解,价值为45

    ⑥ 当前活结点队列的队首为F, 儿子结点L、M为可行叶结点,价值为50、25

    ⑦ G为最后一个扩展结点,儿子结点N、O均为可行叶结点,其价值为25和0

    ⑧ 活结点队列为空,算法结束,其最优值为50

    注:活结点就是不可再进行扩展的节点,也就是两个儿子还没有全部生成的节点

    3. 优先队列式分支限界法

    3.1 以活结点价值为优先级准则

    a297291bb531ba00fc1eab200901bf2f.png

    步骤:

    ①用一个极大堆表示活结点表的优先队列,其优先级定义为活结点所获得的价值。初始为空。

    ②由A开始搜索解空间树,其儿子结点B、C为可行结点,加入堆中,舍弃A。

    ③B获得价值45,C为0. B为堆中价值最大元素,并成为下一扩展结点。

    ④ B的儿子结点D是不可行结点,舍弃。E是可行结点,加入到堆中。舍弃B。

    ⑤ E的价值为45,是堆中最大元素,为当前扩展结点。

    ⑥ E的儿子J是不可行叶结点,舍弃。K是可行叶结点,为问题的一个可行解价值为45。

    ⑦ 继续扩展堆中唯一活结点C,直至存储活结点的堆为空,算法结束。

    ⑧ 算法搜索得到最优值为50,最优解为从根结点A到叶结点L的路径(0,1,1)。

    3.2 以限界函数为优先级准则

    5846173a2c961f76f3b9b7616affce64.png

    应用贪心法求得近似解为(1, 0, 0, 0),获得的价值为40,这可以作为0/1背包问题的下界。

    如何求得0/1背包问题的一个合理的上界呢?考虑最好情况,背包中装入的全部是第1个物品且可以将背包装满,则可以得到一个非常简单的上界的计算方法:

    b=W×(v1/w1)=10×10=100。于是,得到了目标函数的界[40, 100]。

    所以我们定义限界函数为:

    495a9fdb3a39c9307fd128cfdb899d31.png

    再来画状态空间树的搜索图:

    d5d52023dd32fbe041232606f68974b2.png

    步骤:

    ① 在根结点1,没有将任何物品装入背包,因此,背包的重量和获得的价值均为0,根据限界函数计算结点1的目标函数值为10×10=100;

    ② 在结点2,将物品1装入背包,因此,背包的重量为4,获得的价值为40,目标函数值为40 + (10-4)×6=76,将结点2加入待处理结点表PT中;在结点3,没有将物品1装入背包,因此,背包的重量和获得的价值仍为0,目标函数值为10×6=60,将结点3加入表PT中;

    ③ 在表PT中选取目标函数值取得极大的结点2优先进行搜索;

    ④ 在结点4,将物品2装入背包,因此,背包的重量为11,不满足约束条件,将结点4丢弃;在结点5,没有将物品2装入背包,因此,背包的重量和获得的价值与结点2相同,目标函数值为40 + (10-4)×5=70,将结点5加入表PT中;

    ⑤在表PT中选取目标函数值取得极大的结点5优先进行搜索;

    ⑥ 在结点6,将物品3装入背包,因此,背包的重量为9,获得的价值为65,目标函数值为65 + (10-9)×4=69,将结点6加入表PT中;在结点7,没有将物品3装入背包,因此,背包的重量和获得的价值与结点5相同,目标函数值为40 + (10-4)×4=64,将结点6加入表PT中;

    ⑦ 在表PT中选取目标函数值取得极大的结点6优先进行搜索;

    ⑧ 在结点8,将物品4装入背包,因此,背包的重量为12,不满足约束条件,将结点8丢弃;在结点9,没有将物品4装入背包,因此,背包的重量和获得的价值与结点6相同,目标函数值为65;

    ⑨ 由于结点9是叶子结点,同时结点9的目标函数值是表PT中的极大值,所以,结点9对应的解即是问题的最优解,搜索结束。

    总结:

    ★ 剪枝函数给出每个可行结点相应的子树可能获得的最大价值的上界。

    ★ 如这个上界不会比当前最优值更大,则可以剪去相应的子树。

    ★ 也可将上界函数确定的每个结点的上界值作为优先级,以该优先级的非增序抽取当前扩展结点。由此可快速获得最优解。

    展开全文
  • ## 1. 问题描述 ##设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i(1<= i <=n)装入背包,则有价值为pi .... 队列式分支限界法 ##可以通过画分支限界法状态空间树的搜索图来理解具...

    ## 1. 问题描述 ##

    设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i(1<= i <=n)装入背包,则有价值为pi . 目标是找到一个方案, 使得能放入背包的物体总价值最高.

    设N=3, W=(16,15,15),   P=(45,25,25), C=30(背包容量)

    ## 2. 队列式分支限界法 ##

    可以通过画分支限界法状态空间树的搜索图来理解具体思想和流程

    每一层按顺序对应一个物品放入背包(1)还是不放入背包(0)

    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY0OTk5Nw_size_16_color_FFFFFF_t_70]

    步骤:

    **①** 用一个队列存储活结点表,初始为空

    **②** A为当前扩展结点,其儿子结点B和C均为可行结点,将其按从左到右顺序加入活结点队列,并舍弃A。

    **③** 按FIFO原则,下一扩展结点为B,其儿子结点D不可行,舍弃;E可行,加入。舍弃B

    **④** C为当前扩展结点,儿子结点F、G均为可行结点,加入活结点表,舍弃C

    **⑤** 扩展结点E的儿子结点J不可行而舍弃;K为可行的叶结点,是问题的一个可行解,价值为45

    **⑥** 当前活结点队列的队首为F, 儿子结点L、M为可行叶结点,价值为50、25

    **⑦** G为最后一个扩展结点,儿子结点N、O均为可行叶结点,其价值为25和0

    **⑧** 活结点队列为空,算法结束,其最优值为50

    注:活结点就是不可再进行扩展的节点,也就是两个儿子还没有全部生成的节点

    ##  3. 优先队列式分支限界法 ##

    ### 3.1 以活结点价值为优先级准则 ###

    ![在这里插入图片描述][format_png]

    步骤:

    **①** 用一个极大堆表示活结点表的优先队列,其优先级定义为活结点所获得的价值。初始为空。

    **②** 由A开始搜索解空间树,其儿子结点B、C为可行结点,加入堆中,舍弃A。

    **③** B获得价值45,C为0. B为堆中价值最大元素,并成为下一扩展结点。

    **④** B的儿子结点D是不可行结点,舍弃。E是可行结点,加入到堆中。舍弃B。

    **⑤** E的价值为45,是堆中最大元素,为当前扩展结点。

    **⑥** E的儿子J是不可行叶结点,舍弃。K是可行叶结点,为问题的一个可行解价值为45。

    **⑦** 继续扩展堆中唯一活结点C,直至存储活结点的堆为空,算法结束。

    **⑧** 算法搜索得到最优值为50,最优解为从根结点A到叶结点L的路径(0,1,1)。

    ### 3.2 以限界函数为优先级准则 ###

    ![在这里插入图片描述][format_png 1]

    应用贪心法求得近似解为(1, 0, 0, 0),获得的价值为40,这可以作为0/1背包问题的下界。

    如何求得0/1背包问题的一个合理的上界呢?考虑最好情况,背包中装入的全部是第1个物品且可以将背包装满,则可以得到一个非常简单的上界的计算方法:

    b=W×(v1/w1)=10×10=100。于是,得到了目标函数的界\[40, 100\]。

    所以我们定义限界函数为:

    ![在这里插入图片描述][format_png 2]

    再来画状态空间树的搜索图:

    ![在这里插入图片描述][format_png 3]

    步骤:

    **①** 在根结点1,没有将任何物品装入背包,因此,背包的重量和获得的价值均为0,根据限界函数计算结点1的目标函数值为10×10=100;

    **②** 在结点2,将物品1装入背包,因此,背包的重量为4,获得的价值为40,目标函数值为40 + (10-4)×6=76,将结点2加入待处理结点表PT中;在结点3,没有将物品1装入背包,因此,背包的重量和获得的价值仍为0,目标函数值为10×6=60,将结点3加入表PT中;

    **③** 在表PT中选取目标函数值取得极大的结点2优先进行搜索;

    **④** 在结点4,将物品2装入背包,因此,背包的重量为11,不满足约束条件,将结点4丢弃;在结点5,没有将物品2装入背包,因此,背包的重量和获得的价值与结点2相同,目标函数值为40 + (10-4)×5=70,将结点5加入表PT中;

    **⑤** 在表PT中选取目标函数值取得极大的结点5优先进行搜索;

    **⑥** 在结点6,将物品3装入背包,因此,背包的重量为9,获得的价值为65,目标函数值为65 + (10-9)×4=69,将结点6加入表PT中;在结点7,没有将物品3装入背包,因此,背包的重量和获得的价值与结点5相同,目标函数值为40 + (10-4)×4=64,将结点6加入表PT中;

    **⑦** 在表PT中选取目标函数值取得极大的结点6优先进行搜索;

    **⑧** 在结点8,将物品4装入背包,因此,背包的重量为12,不满足约束条件,将结点8丢弃;在结点9,没有将物品4装入背包,因此,背包的重量和获得的价值与结点6相同,目标函数值为65;

    **⑨** 由于结点9是叶子结点,同时结点9的目标函数值是表PT中的极大值,所以,结点9对应的解即是问题的最优解,搜索结束。

    **总结:**

    **★** 剪枝函数给出每个可行结点相应的子树可能获得的最大价值的上界。

    **★** 如这个上界不会比当前最优值更大,则可以剪去相应的子树。

    **★** 也可将上界函数确定的每个结点的上界值作为优先级,以该优先级的非增序抽取当前扩展结点。由此可快速获得最优解。

    [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY0OTk5Nw_size_16_color_FFFFFF_t_70]: /images/1611504876025.png

    [format_png]: /images/1611504847186.png

    [format_png 1]: /images/1611504829634.png

    [format_png 2]: /images/1611504811575.png

    [format_png 3]: /images/1611504787574.png

    展开全文
  • 分支限界法解决01背包问题 实验报告(c++ 版)

    千次阅读 多人点赞 2020-05-14 22:58:26
    应用贪心求得近似解为(1, 0, 0, 0),获得的价值为40,这可以作为0/1背包问题的下界。 如何求得0/1背包问题的一个合理的上界呢?考虑最好情况,背包中装入的全部是第1个物品且可以将背包装满,则可以得到

    问题描述

    设有n个物体和一个背包,物体i的重量为wi价值为pi ,背包的载荷为M, 若将物体i(1<= i <=n)装入背包,则有价值为pi . 目标是找到一个方案, 使得能放入背包的物体总价值最高.
    设n=3 ,c=10, w={4, 7 ,5,3} p={40,42,25,12}

    应用贪心法求得近似解为(1, 0, 0, 0),获得的价值为40,这可以作为0/1背包问题的下界。
    如何求得0/1背包问题的一个合理的上界呢?考虑最好情况,背包中装入的全部是第1个物品且可以将背包装满,则可以得到一个非常简单的上界的计算方法:
    **b=W×(v1/w1)=10×10=100。**于是,得到了目标函数的界[40, 100]。

    在这里插入图片描述

    分析:

    1 在根结点1,没有将任何物品装入背包,因此,背包的重量和获得的价值均为0,根据限界函数计算结点1的目标函数值为10×10=100;

    2 在结点2,将物品1装入背包,因此,背包的重量为4,获得的价值为40,目标函数值为40 + (10-4)×6=76,将结点2加入待处理结点表PT中;在结点3,没有将物品1装入背包,因此,背包的重量和获得的价值仍为0,目标函数值为10×6=60,将结点3加入表PT中;

    3 在表PT中选取目标函数值取得极大的结点2优先进行搜索;

    4 在结点4,将物品2装入背包,因此,背包的重量为11,不满足约束条件,将结点4丢弃;在结点5,没有将物品2装入背包,因此,背包的重量和获得的价值与结点2相同,目标函数值为40 + (10-4)×5=70,将结点5加入表PT中;

    5 在表PT中选取目标函数值取得极大的结点5优先进行搜索;

    6 在结点6,将物品3装入背包,因此,背包的重量为9,获得的价值为65,目标函数值为65 + (10-9)×4=69,将结点6加入表PT中;在结点7,没有将物品
    3装入背包,因此,背包的重量和获得的价值与结点5相同,目标函数值为40 + (10-4)×4=64,将结点6加入表PT中;

    7 在表PT中选取目标函数值取得极大的结点6优先进行搜索;

    8 在结点8,将物品4装入背包,因此,背包的重量为12,不满足约束条件,将结点8丢弃;在结点9,没有将物品4装入背包,因此,背包的重量和获得的价值与结点6相同,目标函数值为65;

    9 由于结点9是叶子结点,同时结点9的目标函数值是表PT中的极大值,所以,结点9对应的解即是问题的最优解,搜索结束。

    代码实现

    #include<bits/stdc++.h>
    using namespace std;
    const int N=100;
    const int inf=0x3f3f3f3f;
    typedef long long ll;
    class HeadNode{
    public:
        double upper,prize,weight;//upper:节点上界,节点价值,节点重量
        int leve,x[N];//
    };
    
    stack<HeadNode>high;
    
    double w[N],p[N],cw,cp,c;
    int n;
    int cmp(int x,int y)
    {
        return p[x]/w[x]>p[y]/w[y];
    }
    void add(double up,double cp,double cw,bool ch,int leve)//存放节点
    {
        HeadNode be;//生成一个空节点
        be.upper=up;
        be.prize=cp;
        be.weight=cw;
        be.leve=leve;
        if(leve<=n)
        {
            high.push(be);
        }
    }
    double MaxBound(int j)//更新上界
    {
        double left=c-cw,b=cp;//left:剩余的容量,b:此时的价值
        while(j<=n&&w[j]<=left)//通过单位体积价值算出理想情况下的最优解
        {
            left-=w[j];
            b+=p[j];
            j++;
        }
        if(j<=n)
            b+=p[j]/w[j]*left;
    
        return b;
    }
    int bfs()
    {
       int i=1,cw=0,cp=0;//初始在第一层,当前重量为0,当前价值为0
       double bestp=0,up=MaxBound(1);//bestp:最优解,up=MaxBound(1):在根节点时候的上界
       while(1)//(FIFO队列式分支限界法)此处可改为 priority_queue:优先队列,每次上界最大的在上面
       {
    
           double wt=cw+w[i];//搜索左子树的可行解
           if(wt<=c)//更新
           {
               bestp=max(bestp,cp+p[i]);//更新可行解
               add(up,cp+p[i],cw+w[i],true,i+1);//将此节点放入栈中
           }
           up=MaxBound(i+1);//右节点不放
           if(up>=bestp)//右节点可能含有最优解
           {
               add(up,cp,cw,false,i+1);
           }
           if(high.empty())return bestp;//当栈为空的时候,此时的bestp就是最优解
           HeadNode node=high.top();//把栈顶的点拿出来
           high.pop();
           cw=node.weight;cp=node.prize;up=node.upper;
           i=node.leve;
       }
    
    }
    int main()
    {
    
        cin>>n>>c;//n个物品,背包容量为c
    
        for(int i=1;i<=n;i++)
            cin>>w[i];
    
        for(int i=1;i<=n;i++)
            cin>>p[i];
        sort(p+1,p+1+n,cmp);
        cout<<bfs()<<endl;
    
    }
    /*
    4 9
    3 2 5 4
    66 40 95 40
    
    161
    
    4 5
    1 2 3 4
    2 4 4 5
    
    8
    
    3 30
    16 15 15
    45 25 25
    
    50
    */
    
    

    测试数据

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    蟹蟹你耐心的看完,比心❤

    在这里插入图片描述

    展开全文
  • 分支限界法01背包问题的解.rar c语言 已调通
  • 分支限界法求解01背包问题

    千次阅读 2020-12-18 20:24:52
    每个节点存储物品在树中的层次,表示已经对多少个物品做出了选择,当前状态放入背包的总价值和重量。 #include <bits/stdc++.h> using namespace std; const int N = 110; struct stone{ int v, w; stone()...

    使用优先队列,求最大价值
    首先按照性价比排序
    bound函数表示当前状态之后的选择都是理想的,这样能到达的理想最大值
    每个节点存储物品在树中的层次,表示已经对多少个物品做出了选择,当前状态放入背包的总价值和重量。

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 110;
    struct stone{
    	int v, w;
    	stone(){
    		v =  w = 0;
    	}
    	bool operator < (stone b) const {
    		return v/w > b.v/b.w;
    	}
    }item[N];
    
    struct node{
    	int level, cv, cw;
    	float bound;
    	bool operator< (const node& b) const{
    		return bound > b.bound;
    	}
    };
    
    int best, W, n;
    inline void Initialize(priority_queue<node> &Q){
    	while(Q.size()) Q.pop();
    }
    
    float bound(node& p){
    	int left = W-p.cw;
    	float val = p.cv;
    	int i;
    	
    	for(i = p.level; i <= n && item[i].w <= left; i++){
    		left -= item[i].w;
    		val += item[i].v;
    	}
    	if(i <= n) val += item[i].v*1.0/item[i].w*left;
    	return val;
    }
    priority_queue<node> PQ;
    void knapsack(){
    	node u, v;
    	Initialize(PQ);
    	v = {0,0,0,0};
    	best = 0;
    	v.bound = bound(v);
    	PQ.push(v);
    	while(PQ.size()){
    		v = PQ.top();
    		PQ.pop();
    		if(v.level == n) continue;
    		if(v.bound > best){
    			u.level = v.level+1;
    			u.cw = v.cw+item[u.level].w;
    			u.cv = v.cv+item[u.level].v;
    			//printf("%d %d\n", u.cw, u.cv);
    			if(u.cw <= W && u.cv > best)
    				best = u.cv;
    			u.bound = bound(u);
    			if(u.bound > best) PQ.push(u);
    			u.cw = v.cw; u.cv = v.cv;
    			u.level = v.level+1;
    			u.bound = bound(u);
    			if(u.bound > best) PQ.push(u);
    		}
    	}
    }
    int main(){
    	scanf("%d%d", &n, &W);
    	for(int i = 1; i <= n; i++) scanf("%d", &item[i].w);
    	for(int i = 1; i <= n; i++) scanf("%d", &item[i].v);
    	sort(item+1, item+1+n);
    	knapsack();
    	printf("%d\n", best);
    	return 0;
    }
    /*
    4 7
    3 5 2 1
    9 10 7 4
    
    20
    */
    
    展开全文
  • 分支限界法解决零一背包问题

    千次阅读 2020-05-29 21:11:04
    解决背包问题时,可以直接使用贪心进行求解,思路也容易理解:先将物品的性价比进行排序,然后从高到低进行选取,保证选取的物品是当前最优选择。由于物件可分得缘故,所以每一步都可行。因此每一步可行以及每...
  • 《算法笔记分支限界法01背包问题》由会员分享,可在线阅读,更多相关《算法笔记分支限界法01背包问题(12页珍藏版)》请在人人文库网上搜索。1、问题描述给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的...
  • 转载于:https://www.cnblogs.com/chihaoyuIsnotHere/p/10007086.html
  • 分支限界法求解01背包

    千次阅读 2020-06-01 09:51:12
    0-1背包问题:给定n种物品和一背包。物品i的重量是wi, 其价值为Vi, 背包的容量为C。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大?在选择装入背包的物品时,对每种物品i可以选择这个物品的一部分...
  • 基于回溯法和分支限界法求解01背包问题 问题描述 现有n个物品,1个背包。对物品i,其价值为viv_ivi​ ,重量为WiW_iWi​,背包的容量为WWW,如何选取物品使得背包里转入物品的总价值最大? 在约束条件为:选取物品的...
  • 利用分支限界法解决01背包和货郎担问题详细步骤       posted @ 2018-11-23 13:48  Charlie_ODD  阅读(...)  评论(...)  编辑  收藏 ...
  • //分支限界法求0/1背包问题的解 void main() { init(7.0); sortpw(); double max = bbKnapsack(); cout(double cc) { c = cc; cw = 0.0; cp = 0.0; bestp = 0.0; } void sortpw() { double pw[ARRAY_LENGTH]; for ...
  • 运用分支定界法(分支限界法)解决01背包问题

    万次阅读 多人点赞 2018-12-05 20:38:42
    解决该题目运用到的数据结构有:优先队列、二叉树、存放物品基本信息的数组 这里主要就是构建二叉树,二叉树节点的属性有 weight(当前总容量) value(当前总价值) layer(当前层级,用来判断是否为叶子节点)...
  • 分支限界法解决0-1背包问题

    千次阅读 2020-05-27 20:56:34
    0-1背包问题我们已经说过很多次了,这次是用最近学的分支限界法解决。分支限界法就是利用队列或者优先队列在储存解空间树的活结点,并每次弹出一个作为扩展结点,是一种广度优先遍历,区别于回溯法的深度优先遍历。...
  • 1、分支限界法介绍分支限界法类似于回溯法,也是在问题的解空间上搜索问题解的算法。一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解;而分支限界法的求解目标...
  • 本人此时还是一名研一的小菜鸡,刚学会了这个算法...还有系列文章动态规划01背包问题,回溯01背包问题哈,需要的化以下是链接: 动态规划:https://blog.csdn.net/qq_29051107/article/details/10339449...
  • 分支限界法0-1背包问题 示例输入(规定物品数量为10,背包容量为50,输入为20个数,前十个为物品重量,后十个数为物品价值): 12 3 11 5 6 8 9 4 7 10 6 2 7 3 2 9 8 10 4 5 示例输出(最大价值): 44
  • 计算机算法设计与分析 课后习题 计算机算法设计与分析 课后习题
  • 算法分析 | 分支限界法 | 01背包问题

    千次阅读 2020-02-19 15:39:37
    分支限界法是对树的广度遍历,需要用到<queue>数据结构.而且每个状态都是一个数据结构实体 状态应该表示如下几个属性: int cp //已放入物品总价值 int rp //剩余物品的总价值 int rw //剩...
  • 分支限界法】求解0/1背包问题

    万次阅读 多人点赞 2019-07-15 19:39:56
    问题描述 0/1背包问题。假设有4个物品,其重量分别为(4, 7, 5, 3),价值分别为(40, 42, 25, 12),...应用贪心求得近似解为(1, 0, 1, 0),获得的价值为65,这可以作为0/1背包问题的下界。   如何求得0...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 997
精华内容 398
关键字:

分支限界法解决01背包