0-1背包-回溯法

news/2024/7/24 9:07:23

算法描述:

0-1背包的回溯法,与装载问题的回溯法十分相似。在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树进行搜索。否则将右子树剪去。

  计算右子树上界的更好算法是:

    将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包。

算法实现:

  由Bound函数计算当前节点处的上界。

  类Knap的数据成员记录解空间树的节点信息,以减少参数传递及递归调用所需的栈空间。

  在解空间树的当前扩展结点处,仅当要进入右子树时,才计算上界bound,以判断是否可将右子树剪去。

  进入左子树时不需要计算上界,因为它与其父节点的上界相同。

算法实现:(代码有点小问题,正在修改中)

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
template <class Typew,class Typep>
class Knap{
        friend Typep Knapsack(Typep *,Typew *,Typew,int);
        private:
                Typep Bound(int i);
                void Backtrack(int i);
                Typew c;//背包容量
                int n;//物品数
                Typew * w;//物品重量数组
                Typep * p;//物品价值数组
                Typew cw;//当前重量
                Typep cp;//当前价值
                Typep bestp;//当前最优价值
};
template <class Typew,class Typep>
void Knap<Typew,Typep>::Backtrack(int i)
{
        if(i>n)//到达叶子
        {
                bestp = cp;
                return;
        }
        if(cw+w[i] <= c)//进入左子树
        {
                cw += w[i];
                cp += p[i];
                Backtrack(i+1);
                cw -= w[i];
                cp -= p[i];
        }
        if(Bound(i+1)>bestp)//进入右子树
                Backtrack(i+1);
}
template <class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i)//计算上界
{
        Typew cleft = c- cw;//剩余容量
        Typep b = cp;
        while(i<=n && w[i]<=cleft)//以物品单位重量价值递减序装入物品
        {
                cleft -= w[i];
                b += p[i];
                i++;
        }
        //装满背包
        if(i<=n)
                b+=p[i]*cleft/w[i];

        return b;
}
class Object
{
        friend int Knapsack(int *,int *,int,int);
public:
        int operator <= (Object a)const
        {
                return (d >= a.d);
        }
private:
        int ID;
        float d;
};
int compare (const void * a, const void * b) 
{ 
  return ( *(int*)a - *(int*)b );
}
template <class Typew,class Typep>
Typep Knapsack(Typep p[],Typew w[],Typew c,int n)
{
        int i;
        //初始化
        int W = 0;
        int P = 0;
        Object* Q = new Object[n];
        for(i=0;i<n;i++)
        {
        //        cout<<p[i]<<" "<<w[i]<<endl<<"-------------------------"<<endl;
                Q[i].ID = i;
                Q[i].d = 1.0*p[i]/w[i];
        //        cout<<Q[i].ID<<" "<<Q[i].d<<endl<<"----------------------"<<endl;
                P += p[i];
                W += w[i];
        //        cout<<P<<" "<<W<<endl<<endl; 
        }
        if(W<=c)
                return P;//装入所有物品
        //依物品单位重量价值排序
        qsort (Q,n, sizeof(int), compare);
        Knap<Typew,Typep> K;
        K.p = new Typep [n+1];
        K.w = new Typew [n+1];
        for(i =1;i<=n;i++)
        {
                K.p[i] = p[Q[i-1].ID];
                K.w[i] = w[Q[i-1].ID];
        }
        K.cp = 0;
        K.cw = 0;
        K.n = n;
        K.bestp = 0;
        K.Backtrack(1);
//        cout<<K.bestp<<endl;
        delete [] Q;
        delete [] K.w;
        delete [] K.p;

        
        return K.bestp;
}
int main()
{

        int p[4] = {9,10,7,4};
        int w[4]= {3,5,2,1};
        int num = Knapsack(p,w,7,4);
        cout<<num<<endl;
        return 0;
}

http://www.niftyadmin.cn/n/1052014.html

相关文章

SQL中利用TRIGGER更新自身表的某个字段

功能很简单&#xff0c;如果某个字段修改了&#xff0c;将本表的另个字段进行更新 直接将代码贴上。 CodeALTER TRIGGER [dbo].[TR_MS_USER_PASSWORD_U] ON [dbo].[MS_USER] FOR UPDATEAS SET NOCOUNT ONIF UPDATE(PASSWORD) BEGIN UPDATE [dbo].[MS_USER] …

idea插件开发(1)

下载开发SDK https://github.com/JetBrains/intellij-community

PreferenceActivity的使用

PreferenceActivity的使用&#xff01; 一般都是自己学习&#xff0c;看到了有用处的地方&#xff0c;上网搜一搜&#xff0c;然后转载保存。注明转载出处&#xff0c;不算侵权&#xff0c;嘿嘿…… 转载自&#xff1a;http://hi.baidu.com/willidie/item/a30a87101930f59699ce…

Codeforces Round #133 (Div. 2) C. Hiring Staff 想法题目

http://codeforces.com/problemset/problem/216/C 题意&#xff1a; 在Berland法律规定每个工人的工作是这样的&#xff1a;它必须连续工作n天&#xff0c;然后休息m天&#xff0c;然后才能继续工作n天休息m天也即他的工作时间为[x, x  1, ..., x  n - 1], [x  m  …

HTC G7 搜索和感光按键修改

1.开启R.E管理器&#xff0c;进入根目录的 /system/usr/keylayout/&#xff0c;找到qwerty.kl文件&#xff0c;开启可读写权限&#xff0c;为了安全起见&#xff0c;可以先将这个文件复制到SD卡上备份。修改搜索键设置&#xff1a;长按qwerty.kl文件&#xff0c;选择用文本编辑…

js动态创建json类型

新建群asp.net相关技术讨论群205914059&#xff0c;快来人呀 废话少说&#xff1a;json是一个特有的键值对数组类型。既然是数组类型那么我们就可以这样定义 1.先定义数组 var Data []; 2.键值对 对象名&#xff1a;值{ "id": i, "title": titleStr, &quo…

打开网址的方式也有讲究

今天遇到了一个小小的错误&#xff0c;却花去了不少的时间&#xff0c;比较郁闷&#xff0c;最后在不经意间解决了。 这两天正在做一个类似教务系统的管理软件&#xff0c;其中有些东西和之前做的新闻发布系统类似&#xff0c;就想着在这基础上改造下后拿来用&#xff0c;可运行…

Dll注入经典方法完整版

总结一下基本的注入过程&#xff0c;分注入和卸载 注入Dll&#xff1a; 1&#xff0c;OpenProcess获得要注入进程的句柄 2&#xff0c;VirtualAllocEx在远程进程中开辟出一段内存&#xff0c;长度为strlen(dllname)1; 3&#xff0c;WriteProcessMemory将Dll的名字写入第二步开辟…