精华内容
下载资源
问答
  • MKP多维背包问题,特殊的背包问题,是著名的整数规划问题。要求从多个限制条件中选出满足所有条件的最佳组合,并计算出最优价值。 解题思路 对一个属性进行不超过限制条件的选择(即01背包问题的列出可能性),最后...

    问题描述

    MKP多维背包问题,特殊的背包问题,是著名的整数规划问题。要求从多个限制条件中选出满足所有条件的最佳组合,并计算出最优价值。

    解题思路

    对一个属性进行不超过限制条件的选择(即01背包问题的列出可能性),最后求多个属性的交集,在交集中找到最大价值即可。

    代码实现

    创建输入文本
    输入数据:(第一行第一个是商品个数,第二个是属性个数,第三个是计算出的最优价值;第二行是6个商品每一个的价值;第三行到倒数第二行是属性;最后一行是限制条件,最后一行第一个数是第一个属性的限制条件,第二是第二个属性的限制条件,以此类推,数据格式如下,不要有多余的空格或者空行。)
    6 10 3800
    100 600 1200 2400 500 2000
    8 12 13 64 22 41
    8 12 13 75 22 41
    3 6 4 18 6 4
    5 10 8 32 6 12
    5 13 8 42 6 20
    5 13 8 48 6 20
    0 0 0 0 8 0
    3 0 4 0 8 0
    3 2 4 0 8 4
    3 2 4 8 8 4
    80 96 20 36 44 48 10 18 22 24

    输出数据:

    商品的个数为: 6 属性的个数为: 10
    价值分别为: [100.0, 600.0, 1200.0, 2400.0, 500.0, 2000.0]
    选择第 2 个商品 | 选择第 3 个商品 | 选择第 6 个商品 |
    最大价值为 3800.0 元

    import pandas #需要导入库
    import numpy #需要导入库
    import time
    start = time.time()
    
    class MKP_Object:
        def allPossibility(restrict,attribute, nums):
            #寻找满足限制条件的组合
            parameter1 = [[]]
            element = []
            for i in range(nums):
                parameter2 = []
                for j in parameter1:
                    element=j+[i]
                    if sum(attribute[element])<restrict:
                        parameter2.append(element)
                parameter1 += parameter2
            return parameter1
    
        def last( aggregate1, aggregate2):
            #寻找满足所有限制条件的价值组合
            jiaoji = []
            for i in aggregate1:
                if i not in jiaoji and  i in aggregate2 :
                    jiaoji.append(i)
            return jiaoji
    
    
    if __name__ == '__main__':
        f1 = open("MKP input.txt")
        first_input = f1.read()
        all_data = first_input.split('\n') 
        want_data = []
        bestValue=[]
        data_1th = list(map(float, all_data[0].split()))  # 切割商品数据和约束条件数据
        commodity_number = int(data_1th[0])  # 读入商品数
        constraints_numbers = int(data_1th[1])  # 读入约束条件数
        constraints = list(map(float, all_data[int(len(all_data) - 1)].split()))  # 读入约束条件
        values = list(map(float, all_data[1].split()))  # 读入商品的价值
        cost=pandas.Series(values)
        for i in range(2, constraints_numbers + 2):
            want_data.append(list(map(int, all_data[i].split())))  # 添加数据到列表中
        data_array=numpy.array(want_data)
        property=pandas.Series(data_array[0])
        intersection=MKP_Object.allPossibility(constraints[0],property,commodity_number) #计算第一个属性的所选商品可能性
     
        for i in range(1,constraints_numbers):
            property=pandas.Series(data_array[i])
            propertyPossibility=MKP_Object.allPossibility(constraints[i],property,commodity_number)
            intersection=MKP_Object.last(intersection,propertyPossibility)
         
        for i in intersection:
            bestValue.append(sum(cost[i]))  #将价值之和添加进列表bestValue
        bestValue = numpy.array(bestValue)
        num = numpy.argmax(bestValue)       #读取最大值下标
        intersection = intersection[num]    #获取价格最大值的元素
        print("\n")
        print("商品的个数为:",commodity_number,"   属性的个数为:",constraints_numbers)
        print("价值分别为:",values)
        for i in range(len(intersection)):
            print("选择第",intersection[i]+1,end=" 个商品 | ")
        print("\n最大价值为",max(bestValue),"元")
    
    end = time.time()
    print("程序运行时间为: ",end - start,"s")
    

    该算法借鉴了同学思路,我修改了大部分算法以及数据结构,修改成了自己的思路。如有想法请在评论区发表,一起交流学习

    展开全文
  • 多维背包问题数据集

    2017-12-18 22:21:52
    关于多维背包问题的论文所用的测试集,我在国外网站上找到了,在此分享给大家。
  • MKP多维背包问题,特殊的背包问题,是著名的整数规划问题。要求从多个限制条件中选出满足所有条件的最佳组合,并计算出最优价值。 解题思路 用回溯法计算出每一个属性的所有可能性(不超过限制条件),然后将其加入...

    问题描述

    MKP多维背包问题,特殊的背包问题,是著名的整数规划问题。要求从多个限制条件中选出满足所有条件的最佳组合,并计算出最优价值。

    解题思路

    用回溯法计算出每一个属性的所有可能性(不超过限制条件),然后将其加入列表里,用一个计数方法将其出现数满足m个属性的个数时,即为满足所有限制条件,再取其中最大值即可。

    代码实现

    创建输入文本
    输入数据:(第一行第一个是商品个数,第二个是属性个数,第三个是计算出的最优价值;第二行是6个商品每一个的价值;第三行到倒数第二行是属性;最后一行是限制条件,最后一行第一个数是第一个属性的限制条件,第二是第二个属性的限制条件,以此类推,数据格式如下,不要有多余的空格或者空行。)
    6 10 3800
    100 600 1200 2400 500 2000
    8 12 13 64 22 41
    8 12 13 75 22 41
    3 6 4 18 6 4
    5 10 8 32 6 12
    5 13 8 42 6 20
    5 13 8 48 6 20
    0 0 0 0 8 0
    3 0 4 0 8 0
    3 2 4 0 8 4
    3 2 4 8 8 4
    80 96 20 36 44 48 10 18 22 24

    输出数据:

    商品个数: 6 属性个数: 10
    价值为: [100.0, 600.0, 1200.0, 2400.0, 500.0, 2000.0]
    选中第2个商品,价值 600.0元 | 选中第3个商品,价值 1200.0元 | 选中第6个商品,价值 2000.0元 |
    数据中给定的最佳价值为: 3800.0 元
    算法计算得出的最大值为: 3800.0 元

    import time as t
    start =t.time()
    
    def backtrack(i):   #回溯法计算不同的组合并赋值到posibility列表中
      global curSX,snum
      if i>=n:
          posibility.append(snum[:])
      else:
        if curSX+shuxing[i]<=xztj:
            snum[i]=value[i]
            curSX+=shuxing[i]
            backtrack(i+1)
            curSX-=shuxing[i]
            snum[i]=0
        backtrack(i+1)
    
    def check(num):
        a = 0
        print("正在计算最大值...")
        print("比较中...")
        for i in num:
            if num.count(i)==sp_m and sum(i)>a:
                a = sum(i)
                bestV = i
                print("当前所选的最大价值为:",sum(i),i)
        print('\n')
        print('\n商品个数:',n,"属性个数:",sp_m)
        print("价值为:",value)
        for i in range(len(bestV)):
            if bestV[i]!=0:
                print('选中第%i个商品,价值'%(i+1),value[i],end='元 |  ')
        print("\n数据中给定的最佳价值为:",bv,'元')
        print("算法计算得出的最大值为:",a,'元')
    
    
    if __name__ == '__main__':
        f1 = open("MKP input.txt")  
        first_input = f1.read()
        #print("最开始读入的数据:",first_input)
        first_data = first_input.split() 
        f1.close()
        all_data = [float(s) for s in first_data]  
        #print("切割后的数据:",all_data)
        n = int(all_data[0])  # 读入商品数
        sp_m = int(all_data[1])  # 读入属性个数
        bv = float(all_data[2]) #读入最佳价格
        constraints =list(map(float,all_data[-sp_m:]))  # 读入约束条件
        #print("约束条件为:",constraints)
        value = list(map(float,all_data[3:n+3])) # 读入商品的价值
        #print("商品价值为:",value)
        secend_data = first_input.split('\n') 
        all_shuxing = []
        for i in range(2, sp_m + 2):
            all_shuxing.append(list(map(int, secend_data[i].split()))) 
        #print("属性分别为",all_shuxing)
        curSX = 0   #当前的限制条件数
        posibility = []  # 记录符合各个限制条件的组合
        snum = [0 for i in range(n)]    #遍历的记录,默认设为[0,0,0,0,0....]
        for m in range(0, sp_m):
            print("正在执行计算...")
            xztj = constraints[m]  
            shuxing = all_shuxing[m] 
            backtrack(0)
        posibility = posibility[:-1]    #去除最后一个可能性,因为是都不选的,无意义
        check(posibility)
    
        end = t.time()
        print("所耗时间为:",end - start)
    

    原创算法,如有想法请在评论区发表,一起交流学习。

    展开全文
  • 为将烟花算法应用于离散优化领域并有效求解多维背包问题,构建一种二进制反向学习烟花算法。.首先,通过定义二进制字符串距离、二进制转置算子将烟花算法的爆炸算子、变异算子离散化,构建二进制烟花算.法;其次,...
  • 用遗传算法解决多维背包问题,采用java代码。用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码用遗传算法解决多维背包问题,采用java代码。
  • 非线性多维背包问题定义为具有多个线性约束的凸函数的最小化。 为非线性多维规划问题开发的方法通常用于解决非线性多维背包问题,但是由于大多数方法都没有利用背包问题的特征,因此它们的效率低下或受到限制。 本文...
  • 基于核问题的果蝇优化算法求解多维背包问题
  • 求解多维背包问题的二级协作果蝇优化算法
  • 利用改进的二进制狼群算法求解多维背包问题
  • 针对多维背包问题(MKP), 提出一种基于分布估计算法的混合求解算法. 该算法基于优势种群构建概率模 型, 并基于概率模型采样产生新个体; 同时, 提出一种基于MKP问题信息的修复机制, 有效修复采样后种群中的不可...
  • 针对多维背包问题(MKP) NP-hard、约束强的特点, 提出一种高效的蚁群-拉格朗日松弛(LR) 混合优化算法. 该算法以蚁群优化(ACO) 为基本框架, 并基于LR 对偶信息定义了一种MKP效用指标. ACO使得整体算法具有全局搜索能力...
  • poj1742 多维背包

    2019-01-04 13:39:00
    普通的多维背包做不了,需要优化一下 但是没有学优化。。别的方法也是可以做的 省去一个表示阶段的 i 维度,dp[j]表示面值为j的钱是否被凑出来了,used[j]表示第i种硬币在凑面值为j的时候被用的次数 #include&...

    普通的多维背包做不了,需要优化一下

    但是没有学优化。。别的方法也是可以做的

    省去一个 表示阶段的 i 维度,dp[j]表示面值为j的钱是否被凑出来了,used[j]表示第i种硬币在凑面值为j的时候被用的次数

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define maxn 100005
    
    int n,m,used[maxn],dp[maxn],a[200],c[200];
    
    int main(){
        while(scanf("%d%d",&n,&m),m){
            for(int i=1;i<=n;i++)scanf("%d",&a[i]);
            for(int i=1;i<=n;i++)scanf("%d",&c[i]);
            memset(dp,0,sizeof dp);
            dp[0]=1;
            for(int i=1;i<=n;i++){
                memset(used,0,sizeof used);
                for(int j=a[i];j<=m;j++)
                    if(!dp[j] && dp[j-a[i]] && used[j-a[i]]<c[i])
                        dp[j]=1,used[j]=used[j-a[i]]+1;
            }
            int ans=0;
            for(int i=1;i<=m;i++)
                if(dp[i]) ans++;
            printf("%d\n",ans);
        }
        return 0;
    }

     

    转载于:https://www.cnblogs.com/zsben991126/p/10219376.html

    展开全文
  • 一种有效的基于混合和声搜索的求解多维背包问题的算法
  • hdu 4501多维背包入门

    2014-06-04 20:53:34
    本题属于多维背包,即有多种支付手段去买物品, 求用这些方式能买到的最大价值。 如本题可以用积分, 钱 , 免费拿去,三种方式得到物品, 求得到物品的最大价值。 这就是多维背包, 可以用dp[i][j][k] i表示用积分...
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    /*
    本题属于多维背包,即有多种支付手段去买物品, 求用这些方式能买到的最大价值。
    如本题可以用积分, 钱 , 免费拿去,三种方式得到物品, 求得到物品的最大价值。
    这就是多维背包, 可以用dp[i][j][k] i表示用积分支付, j表示用钱支付。 k表示可以
    免费领取这件物品。
    */
    struct node {
    
        int money;
        int fen;
        int value;
    }s[110];
    
    int dp[110][110][8];
    int v1, v2, m, n;
    
    
    int main()
    {
        int ans;
       while(scanf("%d%d%d%d", &n ,&v1, &v2, &m) != EOF) {
    
            for(int i = 0; i < n; i++)
                scanf("%d%d%d", &s[i].money, &s[i].fen, &s[i].value);
            memset(dp, 0, sizeof(dp));
            for(int i = 0; i < n; i++)
            for(int j = v1; j >= 0; j--) {  //这里不能用j >= S[i].money; 因为当j不能购买时k, l方式可能
                                              //可以购买。所以dp[j][k][l] 仍然要被枚举一次。
    
                for(int k = v2; k >= 0; k--) {
    
                    for(int l = m; l >= 0; l--) {
                        ans = 0;
                        if(j - s[i].money >= 0)
                            ans = max(ans, dp[j-s[i].money][k][l] + s[i].value);
                        if(k - s[i].fen >= 0)
                            ans = max(ans, dp[j][k-s[i].fen][l]+ s[i].value);
                        if(l -1 >= 0)
                            ans = max(ans, dp[j][k][l-1]+ s[i].value);
                        dp[j][k][l] = max(ans, dp[j][k][l]);
                    }
                }
            }
            printf("%d\n", dp[v1][v2][m]);
       }
        return 0;
    }
    

    展开全文
  • 多维背包 0-1 求解器 康斯坦茨应用科学大学曲荣女士的人工智能课程作业 2。 任务是设计和实现基于人口的算法来解决具有多个约束的背包问题。 使用的基准可以在“另请参阅”部分下找到。 它是 OR 库。 入门 运行“npm...
  • DP 多维背包

    2013-03-09 20:20:02
    多维背包,一般是指限制条件多了一个,比如说:每种物体除了重量,还给了体积,而限制条件变成了体积和重量; 这样可以得到了个递推式: dp[i][j][k]=max{dp[i-1][j][k],dp[i-1][j-v[i]][k-w[i]]+a[i]}; 这样的话...
  • 为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛, 提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中, 在搜索过程中, 既考虑解的质量, 又考虑解的分散性。...
  • hdu 4501 多维背包

    2015-08-02 12:33:07
    直接将01背包搬到多维背包不能想当然,有两个细节需要注意下。 1.多个限制条件不能直接放到for循环中限制,因为各个状态是相互不限制的,放到for循环变量中限制是与的关系,放到{}中的限制是或的关系。 错位代码: ...
  • 多维背包问题的一个蚁群优化算法. 蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低...
  • hdu4501(多维背包

    2014-11-16 10:16:43
    题意:多维背包 思路:dp[i][j][k][o]表示前i件物品,花了j元,花了k个积分,拿了o个免费品的最优值,状态转移见代码。
  • dp 二维乃至多维背包

    2018-12-19 13:57:00
    分析:套路是很明显的01背包,但是这时受约束的变量有两个了,这种情况下就该用多维背包了 分析方法一样的,用dp[i][j][k]表示从前i个愿望中挑选总时间和总金钱不超过j,k时的最大愿望数。 则状态转移方程应该为:...
  • 多维背包问题(MKP)是经典的NP难的组合优化问题。引入有导向变异算子的进化算法GM-EA(Guided Mutation EA)来求解该问题,通过结合粒子群优化的方法改进郭涛算法,更好地利用种群中的全局信息,取得较好的效果。...
  • 针对多约束组合优化问题――多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法。首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法。其次,引入病毒生物进化机制和病毒感染操作...
  • 0/1多维背包问题(0/1 MKP)是一个有趣的NP-hard组合优化问题,可以对物流,金融,电信和其他领域中许多具有挑战性的应用程序进行建模。 在0/1 MKP中,给出了一组项目,每个项目都有大小和值,必须将其放入具有一定...
  • 洛谷 P1855 榨取kkksc03 多维背包问题 题解: 其实就是多维的01背包问题。 代码如下: #include<iostream> #include<algorithm> #include<stdio.h> #include<cmath> #include<queue> ...
  • 这是一篇973项目论文,对研究多维背包问题有很高学术价值,值的一看
  • 多维背包数据

    2021-04-27 12:51:09
    80 20 8 7 10 5 9 3 4 1 2 2 3 4 5 1 4 7 8 6 5 4 11 9 7 5 6 2 6 3 6 3 2 5 4 3 1 2 4 8 6 1 5 9 3 4 1 2 2 3 4 5 1 4 7 8 6 5 4 11 9 7 5 6 2 6 3 6 3 2 5 4 3 1 2 4 3 2 4 1 2 5 11 9 7 5 6 2 6 3 6 3 2 5 4 3 1 ...
  • 多维背包(MKP)是组合优化中一个典型的NP难问题,广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法(Modified Binary Differential Evolution algorithm,MBDE)求解MKP问题,算法关键步骤可分为两部分...
  • 多维背包问题 一个用于托管类似小型框架之类的资源库的应用程序,可将启发式和超启发式方法应用于大学背包的多维背包问题。 跑步 只需调用python main.py 。 您可以对其进行编辑以使用您自己创建的功能或我自己创建...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,720
精华内容 688
关键字:

多维背包