精华内容
下载资源
问答
  • 采用混合遗传算法求解多约束背包问题.首先构建多约束背包问题的数学模型,然后采用多维实数编码方式的遗传算法,结合附带染色体库技术、局部启发式算子和扰动算子对问题进行求解,并给出了一个实验实例.实验证明...
  • 基于粒子群算法的多约束背包问题求解方案.pdf
  • 一和零(双约束背包问题) 本题实质上是一个多约束(n<6)的背包问题,求解目标是,在背包刚好装满的情况下,希望让总的 price 最小。物品可以使用无限次。 参考左神体系班学习班第19节:剪贴纸问题(实际上没...

    题目

    https://leetcode.com/problems/shopping-offers/
    在这里插入图片描述

    题解

    类似题目有:leetcode 474. Ones and Zeroes | 474. 一和零(双约束背包问题)

    本题实质上是一个多约束(n<6)的背包问题,求解目标是,在背包刚好装满的情况下,希望让总的 price 最小。物品可以使用无限次。

    参考左神体系班学习班第19节:剪贴纸问题(实际上没参考它,只是想到有这么个题)

    给定一个字符串str,给定一个字符串类型的数组arr,出现的字符都是小写英文
    arr每一个字符串,代表一张贴纸,你可以把单个字符剪开使用,目的是拼出str来
    返回需要至少多少张贴纸可以完成这个任务。
    例子:str= “babac”,arr = {“ba”,“c”,“abcd”}
    ba + ba + c 3 abcd + abcd 2 abcd+ba 2
    所以本题返回2

    由于一些物品是以组合的形式给出的,所以我们先将 list 嵌套 list 转化成数组,方便索引查找。
    然后,因为物品可以单独购买。为了统一方便,我们将可以单独购买的物品也转化成组合的形式,只不过让它们的系数都为 1。

    如下图所示,前两行分别是单独购买 A 物品、单独购买 B 的价格,后两行是 AB 物品组合购买的价格。
    在这里插入图片描述
    然后就是经典的 暴力递归 -> 傻缓存了。本题应该是无法转化成 dp 的,因为它的状态太多了,详见 dp map 中的 key,我的处理方式是将状态压缩成了字符串。后来看题解发现,hashmap 可以直接用 list 作为 key。

    还有,我这个效率超级低,(应该是我为了避免回溯而copy的数组开销比较大),删掉 import 的头文件的话,会超时(这又是 leetcode 的蜜汁特性,带头文件的话运行速度快一些),带着头文件可以 AC。

    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    class Solution {
        int M; // 套餐总数
        int N; // 物品总数
    
        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            N = price.size();
            M = special.size() + price.size();
    
            // 数组化 套餐列表
            int[][] sp = new int[M][N + 1];
            for (int i = 0; i < special.size(); i++) {
                List<Integer> list = special.get(i);
                for (int j = 0; j < N + 1; j++) {
                    sp[i][j] = list.get(j);
                }
            }
            for (int i = special.size(), j = 0; i < M; i++, j++) {
                sp[i][j] = 1;
                sp[i][N] = price.get(j);
            }
    
            // 数组化 购物清单
            int[] need = new int[N];
            for (int i = 0; i < N; i++) {
                need[i] = needs.get(i);
            }
            
            Map<String, Integer> dp = new HashMap<>();
            return process(sp, need, 0, dp);
        }
    
        // 多约束背包问题
        // 物品列表在special中。当前可选择的物品在cur位置,还剩余needs要买的情况下,至少需要多少cost
        public int process(int[][] special, int[] needs, int cur, Map<String, Integer> dp) {
            // 查缓存
            StringBuilder key = new StringBuilder();
            for (int n : needs) { // 状态压缩成字符串
                key.append(n).append(":");
            }
            key.append(cur);
            if (dp.containsKey(key.toString())) return dp.get(key.toString());
    
            if (allZero(needs)) {
                dp.put(key.toString(), 0);
                return 0;
            }
    
            int minCost = Integer.MAX_VALUE;
            for (int p = cur; p < M; p++) { // 当前购买special[p]套餐
                for (int count = 0; canBuy(special, needs, count, p); count++) { // 购买count件p套餐
                    int[] newNeeds = buy(special, needs, count, p);
                    int newCost = process(special, newNeeds, p + 1, dp);
                    if (newCost != Integer.MAX_VALUE) {
                        minCost = Math.min(minCost, count * special[p][N + 1 - 1] + newCost);
                    }
                }
            }
            // 缓存
            dp.put(key.toString(), minCost);
    
            return minCost;
        }
    
        // 当前状态下,如果继续买count件p物品,是否买了不需要的
        public boolean canBuy(int[][] special, int[] needs, int count, int p) {
            for (int k = 0; k < N; k++) {
                if (needs[k] - count * special[p][k] < 0) return false;
            }
            return true;
        }
    
        public int[] buy(int[][] special, int[] needs, int count, int p) {
            int[] newNeeds = new int[N];
            for (int k = 0; k < N; k++) {
                newNeeds[k] = needs[k] - count * special[p][k];
            }
            return newNeeds;
        }
    
        public boolean allZero(int[] needs) {
            for (int n : needs) {
                if (n != 0) return false;
            }
            return true;
        }
    
    }
    

    在这里插入图片描述

    展开全文
  • POJ 3132 双约束背包问题

    千次阅读 2008-10-26 17:44:00
    多重背包的问题是,给定物品,且有物品的数量...或者说,这里的背包有两重的约束,即背包的容量以及背包最多能装的物品的个数都有限制,不妨成为“双约束背包”。 这种背包问题的思考方式是这样的:用两维背包,pack

        多重背包的问题是,给定物品,且有物品的数量限制,问方法种类或者最大的容量等,这里的限制是限制在物品上;

        另外一种约束是限制在背包上,即:背包最多可以装k种物品,每种物品都是无限的(完全)的,问有多少种背包方式。或者说,这里的背包有两重的约束,即背包的容量以及背包最多能装的物品的个数都有限制,不妨成为“双约束背包”。

        这种背包问题的思考方式是这样的:用两维背包,package[a][b],其中a是背包的最大容量,b是背包最多能装的数量,两个都进行约束之后,背包策略如下:

        对于每一种物品,进行完全背包,对于背包容量为j的情况,考察它由b,b-1,b-2,…,1个物品构成,其递归式子为package[j][k]+=package[j-wt[i]][k-1];这里需要注意到是,背包的顺序,是从b倒序到1,也可以从1升序到b,为什么两者没有区别呢?

    1. #include <algorithm>
    2. #include <numeric>
    3. #include <cmath>
    4. #include <iostream>
    5. #include <cstdio>
    6. #include <iomanip>
    7. #include <vector>
    8. using namespace std;
    9. int primes[187],n=0;
    10. bool isPrime[1120];
    11. int package[1121][15];
    12. void getPrime()
    13. {
    14.     int t;
    15.     memset(isPrime,-1,sizeof isPrime);
    16.     for (int i=2;i<1120;++i)
    17.     {
    18.         if(isPrime[i]) primes[n++]=i;
    19.         for (int j=0;j<n && (t=i*primes[j])<1120;++j)
    20.         {
    21.             isPrime[t]=false;
    22.             if(i%primes[j]==0) break;
    23.         }
    24.     }
    25. }
    26. int main()
    27. {
    28.     getPrime();
    29.     int a,b;
    30.     while (scanf("%d%d",&a,&b))
    31.     {
    32.         if(!a && !b) break;
    33.         memset(package,0,sizeof package);
    34.         package[0][0]=1;
    35.         for (int i=0;i<187 && primes[i]<=a;++i)
    36.             for (int j=a;j>=primes[i];--j)
    37.                 for (int k=1;k<=b;++k)
    38.                 package[j][k]+=package[j-primes[i]][k-1];
    39.         printf("%d/n",package[a][b]);
    40.     }
    41.     return 0;
    42. }
    展开全文
  • 这是一个双约束背包问题。此题需要的前置知识,可以参考我之前的博客:算法设计与分析 0-1背包问题 动态规划解法【超详细】 针对本题,思路如下: 在实现上,为了避免 i-1 的越界判断,将整个数组的 i=0 位置空...

    题目

    https://leetcode.com/problems/ones-and-zeroes/
    在这里插入图片描述

    题解

    这是一个双约束的背包问题。此题需要的前置知识,可以参考我之前的博客:算法设计与分析 0-1背包问题 动态规划解法【超详细】

    针对本题,思路如下:
    在这里插入图片描述
    在实现上,为了避免 i-1 的越界判断,将整个数组的 i=0 位置空出来,显得更整洁一些。

    class Solution {
        public int findMaxForm(String[] strs, int m, int n) {
            int L = strs.length;
            int[][] weight = new int[L + 1][2];
            for (int i = 0; i < L; i++) {
                int z = 0;
                int o = 0;
                for (int j = 0; j < strs[i].length(); j++) {
                    if (strs[i].charAt(j) == '0') {
                        z++;
                    } else {
                        o++;
                    }
                }
                weight[i + 1][0] = z;
                weight[i + 1][1] = o;
            }
            int[][][] dp = new int[L + 1][m + 1][n + 1];
            for (int i = 1; i <= L; i++) { // 第i个物品(序号从1开始)
                for (int mFree = 0; mFree <= m; mFree++) { // 背包剩余x容量
                    for (int nFree = 0; nFree <= n; nFree++) { // 背包剩余y容量
                        if (weight[i][0] > mFree || weight[i][1] > nFree) {
                            dp[i][mFree][nFree] = dp[i - 1][mFree][nFree];
                        } else {
                            dp[i][mFree][nFree] = Math.max(dp[i - 1][mFree - weight[i][0]][nFree - weight[i][1]] + 1, dp[i - 1][mFree][nFree]);
                        }
                    }
                }
            }
            return dp[L][m][n];
        }
    }
    

    在这里插入图片描述

    展开全文
  • 基于线性规划解决二重约束完全背包问题,c++代码。实现功能: 输入: 1、背包容量V质量M和物品数量n 2、//每个物品的容量v[i]和质量m[i] 输出: 最大value
  • dp——多约束背包

    2020-07-27 13:38:03
    dp——多约束背包 一、题目描述 题目 N件物品和一个容量是 V的背包,背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。求解将哪些物品装入背包,可使物品总体积不超过背包容量,总...

    dp——多约束背包

    一、题目描述

    题目

    N件物品和一个容量是 V的背包,背包能承受的最大重量是 M。每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。输出最大价值。

    输入格式

    第一行三个整数,N,V,M,用空格隔开,分别表示物品件数、背包容积和背包可承受的最大重量。接下来有 N 行,每行三个整数 vi,mi,wi,用空格隔开,分别表示第 i 件物品的体积、重量和价值。

    输出格式

    输出一个整数,表示最大价值。

    输入样例

    4 5 6
    1 2 3
    2 4 4
    3 4 5
    4 5 6

    输出样例

    8

    数据范围

    0<N≤100,0<V<1000, 0<M≤1000, vi,mi,wi都小于10000

    二、解题思路

    因为题目是最优子结构问题,所以可以采用动态规划来做。

    【数学建模】

    令dp[i][j][k]表示:前i个物品,当背包体积为j,背包能承受的重量为k,时的可以获得的最多的价值

    【状态方程】

    因为这种背包每种物品只能拿一个,所以可以看成一种类似于01背包的背包问题。所以状态方程也可以参考01背包的来写:
    dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-V[i]][k-m[i]]+value[i]);

    注意

    如果j<V[i]或者k<m[j]那么状态转移方程就是:dp[i][j][k]=dp[i-1][j][k]

    原因

    这个状态转移方程得到的原因如下:

    从第i个考虑,比较选还是不选。如果选择第i个物品,那么背包的体积就要≥这个物体的体积,且背包的重量≥物体的重量,最后再加上这个物体的价值,即:dp[i-1][j-V[i]][k-m[i]]+value[i];如果此背包不满足:背包的体积≥这个物体的体积,且背包的重量≥物体的重量,则放弃这一个物品,即:dp[i-1][j][k]。

    【边界(初始化)】

    如果背包的重量或者背包的体积或者选择的物品数量为0,那么背包所能获得的最大价值就是0。所以背包的边界就是dp[i][j][0]=dp[i][0][k]=dp[0][j][k]=0

    三、时间复杂度及扩展

    时间复杂度

    因为需要使用三重for循环,则可以粗略计算时间复杂度就是O(nVm)

    扩展

    如果这个背包的约束不仅仅只有两个而有多个的话,那么时间复杂度也会增长,空间复杂度也会增加,并且没有优化策略

    四、代码

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,V,m,dp[110][1010][1010];
    struct node{
    	int V,m,val;
    }A[110];
    void init()
    {
    	scanf("%d%d%d",&n,&V,&m);
    	for(int i=1;i<=n;i++)
    		scanf("%d%d%d",&A[i].V,&A[i].m,&A[i].val);
    } 
    void solve()
    {
    	for(int i=0;i<=n;i++)//初始化 
    	{
    		for(int j=0;j<=n;j++)
    		{
    			for(int k=0;k<=n;k++)
    				if(i==0||j==0||k==0)
    					dp[i][j][k]=0;
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<A[i].V;j++)//背包的体积不够 
    			for(int k=1;k<=m;k++)
    				dp[i][j][k]=dp[i-1][j][k];
    		for(int j=A[i].V;j<=V;j++)
    		{
    			for(int k=1;k<A[i].m;k++)//背包所能承受的重量不够 
    				dp[i][j][k]=dp[i-1][j][k];
    			for(int k=A[i].m;k<=m;k++)
    				dp[i][j][k]=max(dp[i-1][j-A[i].V][k-A[i].m]+A[i].val,dp[i-1][j][k]);
    		} 
    	}
    	printf("%d",dp[n][V][m]);
    }
    int main()
    {
    	init();
    	solve();
    	return 0;
    } 
    
    展开全文
  • 实现二重约束背包问题c++代码: /**输入参数: * @param m 表示背包的最大容量 * @param m 表示背包的最大质量 * @param n 表示商品个数 * @param a[] 每个商品的容量 * @param b[] 每个商品的质量 * @...
  • 多维多选的背包问题

    万次阅读 2017-11-12 15:47:18
    0-1背包问题是一类典型的组合优化问题,它要求找出n个物体的一个子集使其尽可能的装满容量为W的背包...多约束背包问题等。多选择背包问题定义为有附加约束条件的背包问题,该问题带有互不相关的多选择约束。该问题的特
  • 背包问题

    2018-11-01 22:29:31
    复杂约束背包:背包的物品相互约束或依赖 推荐的材料是背包问题九讲,初步学习了0-1背包和完全背包问题。   2. 0-1背包问题 所有的背包问题都可以由0-1背包演化而来。 2.1 问题定义: 有一些物品,这些物品...
  • 问题描述 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8 i...
  • 1. 0-1背包问题 1.1 题目描述 有一个包和n个物品,包的容量为m,每个物品都有各自的体积和价值,问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时,能够得到的最大价值是多少?[对于每个物品...
  • 前续:[算法][动态规划]动态转移过程与Python实现小样两例(切绳子与跳台阶) 背包问题讲义 如果无法访问码云的代码库,请访问此处:本文源码@Gist 题目描述 有一个重量上限容量为 totaltotaltotal 的背包和 item_num...
  • 01背包问题

    2018-12-14 11:18:14
    二、总体思路:根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现;...
  • 背包问题不单单是一个简单的算法问题,它本质上代表了一大类问题,这类问题实际上是01线性规划问题,其约束条件和目标函数如下: 自从dd_engi在2007年推出《背包问题九讲》之后,背包问题的主要精髓基本已道尽。...
  • 由于涉及三维度的优化问题,此篇主要记录单个区域调度最优情况,类比二维背包问题,两个约束,dp初始化为成本最大值,放入小哥的value为小哥的节约成本,并打印出分配结果。 import pandas as pd import json ...
  • Java 背包问题

    2019-08-12 19:03:33
    背包问题背包1背包2背包3背包4 背包1 常用、常见 代码片. public static void pakege(int [] w,int []v,int maxw) { // int[] w = {3,5,2,6,4};//物品重量 // int[] v = {4,4,3,5,3};//物品价值 // int maxw = ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,952
精华内容 3,180
关键字:

约束背包问题