标签搜索

目 录CONTENT

文章目录

多重背包问题.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 2 阅读 / 5,349 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

多重背包问题

@[toc]

一、题目描述

端午快到了,现在需要做粽子,共有$n$克面粉有$m$种粽子的馅料,然后做 每种粽子对应的馅料共有$ai$克 做该粽子共需要消耗$bi$克馅料和$ci$克面粉做的粽子可以卖$di$元。那么粽子也可以不放馅料,那么$c0$克面粉做的粽子可以卖$d0$元,求最多可以赚多少钱;

  •  输入
    第一行包含4个整数 $n, m, c0和d0$($1 ≤ n ≤ 1000, 1 ≤ m ≤ 10, 1 ≤ c 0, d 0 ≤ 100$)。以下m行中的每行包含4个 整数。在我个行包含编号一个$a i, b i, c i 和di$($1 ≤ a i, b i, c i, d i ≤ 100$)。

  •  输出

求最多可以赚多少钱

  •  例子
输入
10 2 2 1 
7 3 2 100 
12 3 1 10

输出
241
输入
100 1 25 50 
15 5 20 10

输出
200

二、分析

  •  这道题是一个完全背包(多重背包问题),因为其受多个变量的制约。那么我们先明确题意。
  •  这道题的意思:首先你共有n克面粉(无论做何种粽子都需要面粉)
  •  其次你需要做m种粽子,意味着你有m种馅料每种粽子的馅料共有ai克;我们记有馅料的m种粽子为第一大类粽子。没有馅料的粽子为第二大类粽子
  •  第一大类粽子共有m种,做第一大类粽子中的每种粽子都消耗对应粽子馅料bi克,消耗面粉ci克,那么对应做出来的第一大类粽子中的每种粽子收益di
  •  第二大类粽子不消耗馅料,总改种粽子消耗面粉c0克,收益d0
    在这里插入图片描述
  •  这是个多重背包问题,这道题的主要思想是转化为01背包问题,关键来了,怎么转化???粽子的收益取决于粽子的个数,粽子的个数取决于(第一大类和第二大类一共可以作出的粽子的个数),那么我们能否把这些情况合并一下???
  •  对于不放馅料即第二大类粽子假设n克面粉全部用来做第二大类粽子,那么共可以作出多少个第二大类粽子:n/c0(面粉的总克数 / 每个粽子消耗面粉的克数)个。我们假设不放馅料作出的所有粽子是不同种类的(其实是一类,都属于不妨馅料)。那么第二大类的粽子就共有n/c0种,每种粽子都消耗面粉c0克,都收益d0克。
		//标记总的粽子的个数(第一大类和第二大类共可以作出的粽子个数)
        int index = 0;

		//num代表第二大类粽子的总个数:面粉总克数 / 消耗面粉的克数
        int num = n / c0;
        while(num--)
        {
        	//每种粽子消耗c0克面粉
            weight[index] = c0;

			//收益d0
            value[index] = d0;
            index++;
        }

  •  对于放馅料即第一大类粽子,每种粽子受面粉和对应馅料的限制,我们假设n克面粉全部用来做第i种粽子,那么第i种粽子最多可以做多少个呢?那么就取决于n / ci 和ai / bi的大小关系,即第i种粽子最多可以做min(n / ci ,ai / bi)(因为面粉的克数和馅料的克数是相互制约的),我们不妨再次假设每次做出来的第i种粽子也不是同一种类,那么第i种粽子就有min(n / ci ,ai / bi)种,那么对于第一大类m种粽子就共有m * (min(n / ci ,ai / bi))种
//循环输入
        while(m--)
        {
            cin>>all_num>>cons_stu>>cons_flo>>child_value;
            
            //num记录min(n / cons_flo,all_num / cons_stu)的最小值
            //因为这里的粽子是第一大类,其受面粉和馅料的限制,只能取较小的
            num = min(n / cons_flo,all_num / cons_stu);
            
            while(num--)
            {
            	//更新作出每种粽子消耗面粉的克数
                weight[index] = cons_flo;
	
				//更新做出每种粽子的收益
                value[index] = child_value;
                index++;
            }
        }

在这里插入图片描述

  •  经过上面的分解,通过增加粽子的总数消除了馅料对粽子的影响,那么就可以直接转01背包了

01背包问题详解

三、代码

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	//代表面粉的总克数
	int n;

	//粽子(馅料的总数)
	int m;
	
	//不放馅料做粽子消耗面粉的克数
	int c0;
	
	//不放馅料做粽子的收益
    int d0;
    
    while(cin>>n>>m>>c0>>d0)
    {
		//weight[i]代表做第i种粽子消耗面粉的克数
    	vector<int> weight(10000);

		//value[i]代表做第i种粽子消耗面粉的收益
    	vector<int> value(10000);
    	
    	//标记总的粽子的个数(第一大类和第二大类共可以作出的粽子个数)
        int index = 0;

		//num代表第二大类粽子的总个数:面粉总克数 / 消耗面粉的克数
        int num = n / c0;
        while(num--)
        {
        	//每种粽子消耗c0克面粉
            weight[index] = c0;

			//收益d0
            value[index] = d0;
            index++;
        }

		//代表每种粽子总馅料的克数
		int all_num;
	
		//代表做第i种粽子消耗第i种馅料的克数
		int cons_stu;

		//代表做第i种粽子消耗面粉的克数
		int cons_flo;
		
		//代表作出第i种粽子的收益
		int child_value;

		//循环输入
        while(m--)
        {
            cin>>all_num>>cons_stu>>cons_flo>>child_value;
            
            //num记录min(n / cons_flo,all_num / cons_stu)的最小值
            //因为这里的粽子是第一大类,其受面粉和馅料的限制,只能取较小的
            num = min(n / cons_flo,all_num / cons_stu);
            
            while(num--)
            {
            	//更新作出每种粽子消耗面粉的克数
                weight[index] = cons_flo;
	
				//更新做出每种粽子的收益
                value[index] = child_value;
                index++;
            }
        }
        
        //index记录的是总粽子的个数,更新一下即可
        m = index;

		//dp数组,到这里已经完全转化为01背包问题了,
		//直接一01背包的解法即可
        vector<int> dp(10000,0);
        dp[0]=0;
        for(int i = 0;i < m;i++)
        {
        	/*
            for(int j = n;j >= weight[i];j--)
            { 
                dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
            }
            */

			//这种写法已经完全和《01背包问题详解》一致了
            for(int j = n;j >= 0;j--)
            { 
            	if(j < weight[i])
            	{
            		dp[j] = dp[j - 1];
            	}
            	else 
            	{
            		dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
            	}
            }
        }
        
        int ret = 0;
        for(auto e : dp)
        {
           ret = max(e,ret);
        }
        cout<<ret<<endl;
    }
    return 0;
}

四、问题描述

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {

    }
};

五、分析

  •  为什么说这道题是完全背包问题呢?因为01背包问题是已知有限个物品的重量和每个物品的价值,求在背包容量固定的情况下最大的价值
  •  而这道题我们可以把总金额amount作为最大价值,每个硬币的面值作为对应的价值和重量(面值小个数多),但是每个硬币的个数是无限的,我们不知道什么时候结束???
  •  既然是完全背包问题,那么我们是否可以把它转化为01背包问题呢?
  •  有一个背包,最大容量为 amount,有一系列物品 coins,每个物品的重量为 coins[i],每个物品的数量无限。请问有多少种方法,能够把背包恰好装满?
  •  这个问题和01背包问题,有一个最大的区别就是,每个物品的数量是无限的,这也就是传说中的「完全背包问题」,没啥高大上的,无非就是状态转移方程有一点变化而已。
  •  第一步要明确两点,「状态」和「选择」。
  • 状态有两个,就是「背包的容量」和「可选择的物品」,选择就是「装进背包」或者「不装进背包」嘛,背包问题的套路都是这样。
  • 明白了状态和选择,动态规划问题基本上就解决了,只要往这个框架套就完事儿了:
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][...] = 计算(选择1,选择2...)
  •  第二步要明确 dp 数组的定义
  •  首先看看刚才找到的「状态」,有两个,也就是说我们需要一个二维 dp 数组。
  •  dp[i][j] 的定义如下:
  • 若只使用前 i 个物品,当背包容量为 j 时,有 dp[i][j] 种方法可以装满背包。
  • 换句话说,翻译回我们题目的意思就是:
  • 若只使用 coins 中的前 i 个硬币的面值,若想凑出金额 j,有 dp[i][j] 种凑法。
  •  经过以上的定义,可以得到:
  • base case 为 dp[0][..] = 0, dp[..][0] = 1。因为如果不使用任何硬币面值,就无法凑出任何金额;如果凑出的目标金额为 0,那么“无为而治”就是唯一的一种凑法。
  • 我们最终想得到的答案就是 dp[N][amount],其中 N 为 coins 数组的大小。
  •  大致的伪码思路如下:
int dp[N+1][amount+1]
dp[0][..] = 0
dp[..][0] = 1

for i in [1..N]:
    for j in [1..amount]:
        把物品 i 装进背包,
        不把物品 i 装进背包
return dp[N][amount]
  •  第三步,根据「选择」,思考状态转移的逻辑。
  •  注意,我们这个问题的特殊点在于物品的数量是无限的,所以这里和之前的01背包问题有所不同。
  •  如果你不把这第 i 个物品装入背包,也就是说你不使用 coins[i] 这个面值的硬币,那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j],继承之前的结果。
  •  如果你把这第 i 个物品装入了背包,也就是说你使用 coins[i] 这个面值的硬币,那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。
  •  首先由于 i 是从 1 开始的,所以 coins 的索引是 i-1 时表示第 i 个硬币的面值。
  •  dp[i][j-coins[i-1]] 也不难理解,如果你决定使用这个面值的硬币,那么就应该关注如何凑出金额 j - coins[i-1]。
  • 比如说,你想用面值为 2 的硬币凑出金额 5,那么如果你知道了凑出金额 3 的方法,再加上一枚面额为 2 的硬币,不就可以凑出 5 了嘛。
  •  综上就是两种选择,而我们想求的 dp[i][j] 是「共有多少种凑法」,所以 dp[i][j] 的值应该是以上两种选择的结果之和
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= amount; j++) {
        if (j - coins[i-1] >= 0)
            dp[i][j] = dp[i - 1][j] 
                     + dp[i][j-coins[i - 1]];
return dp[N][W]

六、代码

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1,vector<int>(amount + 1,0));

        //base case:
        for (int i = 0; i <= n; i++) 
            dp[i][0] = 1;

        for (int i = 1; i <= n; i++) 
        {
            for (int j = 1; j <= amount; j++)
            {
                if (j - coins[i - 1] >= 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                else 
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][amount];
    }
};

  •  而且,我们可以发现,dp 数组的转移只和 dp[i][..] 和 dp[i-1][..] 有关,所以可以压缩状态,进一步降低算法的空间复杂度
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount + 1,0);

        //base case:
        dp[0] = 1;

        for (int i = 0; i < n; i++) 
        {
            for (int j = 1; j <= amount; j++)
            {
                if (j - coins[i] >= 0)
                    dp[j] = dp[j] + dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

0

评论区