动态规划:完全背包、多重背包[通俗易懂]

动态规划:完全背包、多重背包[通俗易懂]一、问题描述:  完全背包:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。      多重背包:有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、问题描述:

  完全背包:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。    

  多重背包:有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

 

  比较这两个题目以及上次谈到的0-1背包(想看0-1背包的请移步:0-1背包),会发现不同点在于每种背包的数量,01背包是每种只有一件,完全背包是每种无限件,而多重背包是每种有限件。

二、完全背包动态规划过程:

    根据第i种物品放多少件进行决策,所以状态转移方程为

                        动态规划:完全背包、多重背包[通俗易懂]   

         其中F[i-1][j-K*C[i]]+K*W[i]表示前i-1种物品中选取若干件物品放入剩余空间为j-K*C[i]的背包中所能得到的最大价值加上k件第i种物品;

         设物品种数为N,背包容量为V,第i种物品体积为C[i],第i种物品价值为W[i]。

         与01背包相同,完全背包也需要求出NV个状态F[i][j]。但是完全背包求F[i][j]时需要对k分别取0,…,j/C[i]求最大F[i][j]值。

    这样代码应该是三层循环(物品数量,物品种类,背包大小这三个循环),伪代码如下:

F[0][] ← {0}  
  
F[][0] ← {0}  
  
for i←1 to N  
  
    do for j←1 to V  
  
        do for k←0 to j/C[i]  
  
           if(j >= k*C[i])  
  
                then F[i][k] ← max(F[i][k],F[i-1][j-k*C[i]]+k*W[i])  
  
return F[N][V]

很明显,这样一般情况下会超时,需要转化成时间复杂度比较低的在进行求解

  经过思考可以想到完全背包可以转化为01背包:

       因为同种物品可以多次选取,那么第i种物品最多可以选取V/C[i]件价值不变的物品,然后就转化为01背包问题。如果把第i种物品拆成体积为C[i]×2k价值W[i]×2k的物品,其中满足C[i]×2k≤V。即设F[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。那么对于第i种物品的出现,我们对第i种物品放不放入背包进行决策。如果不放那么F[i][j]=F[i-1][j];如果确定放,背包中应该出现至少一件第i种物品,所以F[i][j]种至少应该出现一件第i种物品,即F[i][j]=F[i][j-C[i]]+W[i]。为什么会是F[i][j-C[i]]+W[i]?因为F[i][j-C[i]]里面可能有第i种物品,也可能没有第i种物品。我们要确保F[i][j]至少有一件第i件物品,所以要预留C[i]的空间来存放一件第i种物品。

  状态方程为:

                 动态规划:完全背包、多重背包[通俗易懂]

0-1背包和完全背包的不同:

  从二维数组上区别0-1背包和完全背包也就是状态转移方程就差别在放第i中物品时,完全背包在选择放这个物品时,最优解是F[i][j-c[i]]+w[i]即画表格中同行的那一个,而0-1背包比较的是F[i-1][j-c[i]]+w[i],上一行的那一个。

  从一维数组上区别0-1背包和完全背包差别就在循环顺序上,0-1背包必须逆序,因为这样保证了不会重复选择已经选择的物品,而完全背包是顺序,顺序会覆盖以前的状态,所以存在选择多次的情况,也符合完全背包的题意。状态转移方程都为F[i] = max(F[i],dp[F-c[i]]+v[i])。

三、完全背包代码

  用一维数组实现

#include<cstdio>
#include<algorithm>
using namespace std;
int w[300],c[300],f[300010];
int V,n;
int main()
{
    scanf("%d%d",&V,&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&w[i],&c[i]);
    }
    for(int i=1; i<=n; i++)
        for(int j=w[i]; j<=V; j++)//注意此处,与0-1背包不同,这里为顺序,0-1背包为逆序
            f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("max=%d\n",f[V]);
    return 0;
}

多重背包问题的思路跟完全背包的思路非常类似,只是k的取值是有限制的,因为每件物品的数量是有限制的,状态转移方程为:

    dp[i][v] = max{dp[i – 1][v – k * c[i]] + w[i] | 0 <=k <= n[i]}  

    其中c[i]是物品的数量,和完全背包的不同支出在于完全背包可以取无数件,而多重背包给定了最多能取的数量。这样也是三个循环,分别是背包容量,物品个数和物品种类。这样如果数量比较多的情况,很明显这个做法也会超时,所以我们也要想更优化的方法去完善。

  转化为01背包问题

    转化为01背包求解:把第i种物品换成n[i]件01背包中的物品。考虑二进制的思想,考虑把第i种物品换成若干件物品,使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外,取超过n[i]件的策略必不能出现。

    方法是:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。

    分成的这几件物品的系数和为n[i],表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示,证明我也没看过这里就不贴上了,主要还是需要去理解代码,代码在下面给出。

五、多重背包代码:

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1000000
using namespace std;

int dp[MAX];//存储最后背包最大能存多少
int value[MAX],weight[MAX],number[MAX];//分别存的是物品的价值,每一个的重量以及数量
int bag;

void ZeroOnePack(int weight,int value )//01背包
{
    int i;
    for(i = bag; i>=weight; i--)
    {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}
void CompletePack(int weight,int value)//完全背包
{
    int i;
    for(i = weight; i<=bag; i++)
    {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}

void MultiplePack(int weight,int value,int number)//多重背包
{
    if(bag<=number*weight)//如果总容量比这个物品的容量要小,那么这个物品可以直到取完,相当于完全背包
    {
        CompletePack(weight,value);
        return ;
    }
    else//否则就将多重背包转化为01背包
    {
        int k = 1;
        while(k<=number)
        {
            ZeroOnePack(k*weight,k*value);
            number = number-k;
            k = 2*k;//这里采用二进制思想
        }
        ZeroOnePack(number*weight,number*value);
    }
}
int main()
{
    int n;
    while(~scanf("%d%d",&bag,&n))
    {
        int i,sum=0;
        for(i = 0; i<n; i++)
        {
            scanf("%d",&number[i]);//输入数量
            scanf("%d",&value[i]);//输入价值  此题没有物品的重量,可以理解为体积和价值相等
        }
        memset(dp,0,sizeof(dp));
        for(i = 0; i<n; i++)
        {
            MultiplePack(value[i],value[i],number[i]);//调用多重背包,注意穿参的时候分别是重量,价值和数量
        }
        cout<<dp[bag]<<endl;
    }
    return 0;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164407.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 设置IP地址、子网掩码、网关和DNS(手动获得IP地址默认网关)

    IP地址,子网掩码、默认网关,DNS的设置和工作原理(总结)转载:https://blog.csdn.net/kingshown_WZ/article/details/46423771概念:1.概述IP地址:人们在Internet上为了区分数以亿计的主机而给每台主机分配的一个专门的地址,通过IP地址就可以访问到每台主机。…

  • spring中@EventListener 的详解和使用

    spring中@EventListener 的详解和使用转载:面了个35的程序员,让我莫名的慌了。。。(欢迎关注原文作者公众号:Java充电社)面了个35的程序员,让我莫名的慌了。。。原创路人甲Java路人甲Java2020-05-10收录于话题#Spring高手系列55个内容月底免费送书活动,这两天是最后的机会,大家尽快参与!面试官:看你是85年的我:嗯,35了面试官:那应该经验很丰富了,那我们来聊聊spring吧我:好,这块我用了10几年了,你随便问吧面试官:Spring中的事件用过么?我:用过…

    2022年10月23日
  • CNN垃圾分类_垃圾分类卡通画

    CNN垃圾分类_垃圾分类卡通画基于TensorFlow和Keras的垃圾分类模型本篇博客主要介绍基于TensorFlow和Keras实现垃圾分类模型,目前是一篇占坑的博客,由于该项目目前用于参加比赛,因此暂时不能提供代码,感兴趣的可以私信我一起交流,识别结果如下所示:

  • 获取数据库中所有表名

    获取数据库中所有表名

    2021年10月19日
  • SQLServer2K远程连接问题解决方案(转载自飞狐小屋)

    SQLServer2K远程连接问题解决方案(转载自飞狐小屋)由于特定需求,最近实验室需要远程连接外地的sqlserver2000服务器,最开始怎么连也连不上,出现了很多问题,但是在今天上午,借用实验室的测试条件(一个公网IP,两个教育网静态IP),终于调试通过,也算是完成了老师的任务,在这里写下自己的心得,参考了很多网上的文章和论坛里的问题,希望对有此需要的有帮助。不完善之处,也请留言。废话少说,进入主题。步骤:一看ping服务…

  • 一批SP名单_SP公司

    一批SP名单_SP公司一批SP名单: 端口号(服务号)SP公司名01007广东嘉讯

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号