完全背包问题

Kubrnete
• 阅读 1263

问题描述

有n种物品和一个容量为c的背包,每种物品都就可以选择任意多个,第i种物品的价值为v[i],体积为w[i],求解:在不超过背包容量的情况下,选择放入哪些物品能够使得背包中的价值最大?

跟01背包一样,完全背包也是一个很经典的动态规划问题,不同的地方在于01背包问题中,每件物品最多选择一件;而在完全背包问题中,只要背包装得下,每件物品可以选择任意多件。从每件物品的角度来说,与之相关的策略已经不再是选或者不选了,而是有取0件、取1件、取2件...直到取⌊c/wi⌋(向下取整)件。

在上一篇文章中,我们提到过01背包问题的递推关系:

完全背包问题

认识01背包问题之后,现在让我们来看对于完全背包问题的递归解法:

完全背包的递推关系

我们用V_total(i,j)表示前i种物品放入一个容量为j时的背包获得的最大价值,那么对于第i种物品,我们有k种选择,0 <= k * w[i] <= j,(容量约束条件)即可以选择0、1、2...k件第i种物品,所以递推表达式为:

V_total(i,j) = max{V_total(i-1, j - w[i] * k) + v[i] * k}; (0 <= k * w[i] <= j)

(注:当k=0则为不选,最多可选k=j/w[i]件。在这个范围中找出k种选择种的最优解)

现在我们很容易能够写出对应的递归代码。

理所当然地,我们将用一个数组存储计算结果,如果递归时已经计算过,那么返回该结果。

int V_total(int i, int j)
{
    int value = 0;
    if (i && j) //可选物品个数和初始容量皆不为0
    { 
        if (j < w[i])
            value = V_total(i - 1, j);
        else
            for (int k = 0; k * w[i] <= j; k++)
            {
                int temp = V_total(i - 1, j - w[i] * k) + v[i] * k;
                value = temp > value ? temp : value;
            }
    }
    return value;
}

填表法

当然,有了这个递推关系式,其实也是我们的状态转移方程式,现在我们可以尝试用填表的方式自下而上处理。

比如只有两个物品:物品A:价值5,体积5,物品B:价值8:体积7,背包容量为10,下面开始填表。

完全背包问题

物品1重量V=5,价值P=5,物品2重量V=7,价值P=8。可选物品个数为0和容量为0的选择都为0。

i=1时,若t<10,背包最多只能放下1个物品1,价值为5;当t=10时,能放下2个物品1,因此i=1时的最大值为10。

i=2时,若5<=t<7时,背包能放下1个物品1;当7<=t<10时,背包能放下1个物品2,最大值为8;当t=10时,能放下2个物品1或1个物品2,因此最大值为10。通过求解这些子问题的最优解,我们推导出了全局最优解。

转换代码如下

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= c; j++)
        for (int k = 0; k * w[i] <= j; k++)
            values[i + 1][j] = max(values[i + 1][j], values[i][j - k * w[i]] + k * v[i]);
cout << values[n][c];

和01背包一样,这里效率仍可以继续优化。具体思路这里就不重复介绍了,可以翻看前面的01背包问题动态规划篇。

优化后的状态转移方程为:

V_total(t) = max{V_total(t), V_total(t - wi) + vi}

附完整代码:

#include <bits/stdc++.h>
using namespace std;
int n, c, d;
int v[1002], w[1002], dp[1002];
int main()
{

    cin >> n >> c;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    for (int i = 1; i <= n; i++)
        for (int j = w[i]; j <= c; j++)
            dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
    cout << dp[c];
}

其实完全背包问题也可以转化成01背包问题来求解。因为第i件物品最多选 ⌊c/wi⌋(向下取整) 件,于是可以把第i种物品转化为

体积 j=⌊c/wi⌋件价值相同的物品,然后再对这个01背包问题进行求解。具体留给大家自行解决。如果遇到问题,可以翻开前面关于01背包问题的两篇文章。

总结

完全背包问题跟01背包有很多相似之处,比较一下他们的状态转移方程以及各种解法,就会发现他们其实是异父异母的亲兄弟。

(建议仔细思考其中的区别)

它们的本质区别就是01背包从体积大的开始遍历,这样的话就不能一件物品多次放置。而完全背包是从体积最小的开始遍历,这样的话就会出现一件物品多次放置的特点。这样也就凸显了两种背包的不同,但是这两种都是最基本的背包雏形。

这两个背包问题的关键都在于状态转移方程的寻找,如果对于类似的问题没有思路,可以先尝试找出递归解法,然后自上而下的记忆法便水到渠成了。

当然,最重要的还是解题思路,理解记忆法和填表法的精髓,有助于之后举一反三,去解决类似的延伸问题。

本文转自 https://blog.csdn.net/guanguandaren/article/details/107960802,如有侵权,请联系删除。

点赞
收藏
评论区
推荐文章
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Stella981 Stella981
1年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Stella981 Stella981
1年前
Linux查看GPU信息和使用情况
1、Linux查看显卡信息:lspci|grepivga2、使用nvidiaGPU可以:lspci|grepinvidia!(https://oscimg.oschina.net/oscnet/36e7c7382fa9fe49068e7e5f8825bc67a17.png)前边的序号"00:0f.0"是显卡的代
Stella981 Stella981
1年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
1年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
1年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表:时辰时间24时制子时深夜11:00凌晨01:0023:0001:00丑时上午01:00上午03:0001:0003:00寅时上午03:00上午0
Stella981 Stella981
1年前
Nginx反向代理upstream模块介绍
!(https://oscimg.oschina.net/oscnet/1e67c46e359a4d6c8f36b590a372961f.gif)!(https://oscimg.oschina.net/oscnet/819eda5e7de54c23b54b04cfc00d3206.jpg)1.Nginx反
Wesley13 Wesley13
1年前
Unity3D学习笔记(二十六):MVC框架下的背包系统(1)
MVC背包!(https://oscimg.oschina.net/oscnet/dd09a8a61054c24d33e9fd2e8c3850eab02.png)需求:1、背包格子的装备是可以拖动的2、装备栏的装备也是可以拖动的3、当背包格子的装备拖动到装备栏时,如果是装备类型和装备栏类型是一致的能装上4、背包的装备是按照顺序放在
Stella981 Stella981
1年前
A Mini Locomotive(动态规划 01)
 /\ 题意:选出3个连续的数的个数 为K的区间,使他们的和最大分析: dp\j\\i\max(dp\jk\\i1\value\j\,dp\j1\\i\);dp\j\\i\:从j个数种选出i个连续区间 数值的最大和value\j\:第j个区间内的数的和和背包有点像,但要活用\
Wesley13 Wesley13
1年前
PHP中的NOW()函数
是否有一个PHP函数以与MySQL函数NOW()相同的格式返回日期和时间?我知道如何使用date()做到这一点,但是我问是否有一个仅用于此的函数。例如,返回:2009120100:00:001楼使用此功能:functiongetDatetimeNow(){
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_