首页 > 其他分享 >背包九讲——背包问题求方案数

背包九讲——背包问题求方案数

时间:2024-11-10 22:47:19浏览次数:3  
标签:方案 背包 容量 九讲 问题 01 物品

目录

背包问题求方案数

1. 01 背包问题

题目链接:11. 背包问题求方案数 - AcWing题库

算法实现:

代码实现:

问题变形: 

解决方法:

2. 多重背包问题

3. 完全背包问题

背包问题第八讲——背包问题求方案数

背包问题是一类经典的组合优化问题,通常涉及在限定容量的背包中选择物品,以最大化某种价值或利益。问题的一般描述是:有一个背包,其容量为C;有一组物品,每个物品有重量w和价值v。目标是选择一些物品放入背包,使得它们的总重量不超过背包容量,同时总价值最大。
背包问题涉及到了三种基础的背包:01背包、多重背包、完全背包,我们要根据在这几个背包的基础上去计算在获得最大价值的情况下,有几种方案,并输出方案数。

背包问题求方案数

背包问题是一个组合优化问题,其中背包可以是01背包问题、完全背包问题、多重背包问题等。每种背包问题都有不同的求解方法。这里博主将分别介绍这三种背包问题的基本概念和求解方案数的方法。

1. 01 背包问题

0-1背包问题是指每个物品只有0跟1两种选择即只能选择放或不放,不能分割。给定一组物品,每个物品都有自己的重量和价值,在不超过背包容量的前提下,选择一些物品,使得总价值最大。

求解方案数: 01背包问题的方案数通常不是直接求解的目标,因为可能非常巨大,而且求解最大价值更有意义。但如果需要计算方案数,可以使用动态规划的方法,其中 dp[i][j] 表示考虑前 i 个物品,当背包容量为 j 时的方案数。

题目链接:11. 背包问题求方案数 - AcWing题库

下面我们将以acwing上的题目为例进行 01背包问题的讲解。

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

输出 最优选法的方案数。注意答案可能很大,请输出答案模 109+7109+7 的结果。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数,表示 方案数 模 109+7109+7 的结果。

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例:

2
算法实现:

这既然是01背包基础上改进,那代码就在01背包基础上改进的,选择加一个c[i]数组记录方案数。c[i]表示背包容量为i时最大价值的方案数。当什么也不选择时,也是一种方案,那么c[i]=1。解释一下状态转移方程,f[j]<f[j-v[i]]+w[i]时,说明选择第i个物品价值更大,那就选择,选择了背包容量就要扣除v[i]留给选择第i件物品,相对于背包容量j-v[i]背包容量增加了,选择了它并不会改变方案数,你可以理解一棵树,向左选择,向右不选,当此时背包容量相同时,分别走不同的分支是不同的方案,但是位于同一分支处,面临选不选,我的方案数是不变的,因为选了背包容量就增大了,方案数是在背包容量相等的基础上而言。

所以此时总结一下:

  • 装入新物品,若总价值增大,则更新f[i]和c[i]
  • 装入新物品,若总价值不变,则更新c[i]
  • 装入新物品,若总价值减小,则不用更新       
代码实现:
#include<iostream>
using namespace std;
const int mod=1e9+7;
int n,m;
int v[1005],w[1005];
int f[1005],c[1005];
//f[i]表示背包容量为i时所获得最大价值,c[i]表示背包容量为i时的方案数
int main(){
    cin>>n>>m;
    for(int i=0;i<=m;i++){
        c[i]=1;//什么也不选,自己也是一种方案
    }
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            if(f[j]<f[j-v[i]]+w[i]){//如果选第i件物品价值更大,那就选择,此时价值改变,方案数不变
                f[j]=f[j-v[i]]+w[i];
                c[j]=c[j-v[i]];
            }else if(f[j]==f[j-v[i]]+w[i]){//如果价值相等,获得此价值相对又多了一种方案,方案数相加
                c[j]=(c[j]+c[j-v[i]])%mod;
            }
        }
    }
    cout<<c[m]<<endl;
    return 0;
}

视频讲解: E19 背包DP 求方案数_哔哩哔哩_bilibili


问题变形: 

此题你会发现,当背包容量不同时可能会产生同样的最大价值,如果再考虑上背包容量恰好装满时所获得最大价值的方案数呢?

解决方法:

最开始我们想到的就是在if上多加上一个限定条件,一个很巧妙的方法我们可以在初始化上做一下手脚,保证状态转移可以在c[0]上转移。使得只有恰好装满时才有机会通过c[0]去直接或者间接转移。那些不符合条件的,不能装满的都被过滤掉了,具体大家可以debug看一下过程。


2. 多重背包问题

多重背包问题是指每种物品可以取有限次。给定一组物品,每种物品都有自己的重量、价值和一个数量限制,在不超过背包容量的前提下,选择物品的组合使得总价值最大。

求解方案数: 多重背包问题可以通过动态规划或贪心算法求解。定义 dp[j] 为背包容量为 j 时的方案数。状态转移方程为: dp[j]+=dp[j−weight[i]] 对于每个物品,从 1count[i](物品数量),更新 dp[j]

具体思路先可以按照二进制优化进行拆分,然后再去利用01背包进行求解。 


3. 完全背包问题

完全背包问题是指每种物品可以无限取用,可以理解为无限使用。给定一组物品,每种物品都有一个重量和价值,在不超过背包容量的前提下,选择物品的组合使得总价值最大。

求解方案数: 完全背包问题的方案数可以通过动态规划求解。定义 dp[i][j] 为考虑前 i 个物品,当背包容量为 j 时的方案数。状态转移方程为:dp[i][j]=dp[i−1][j]+dp[i][j−weight[i]] 其中,weight[i] 是第 i 个物品的重量。


上一篇博客:背包九讲——树形背包问题(有依赖的背包)_背包问题 树-CSDN博客

背包问题求具体方案是后面衍生出来的问题,也是经典的背包九讲问题之一,这里以01背包进行详解的,多重背包以及完全背包问题直接套之前的模板,再加上c[i]即可。执笔至此,感触彼多,全文将至,落笔为终,感谢大家支持。下篇更新背包求具体方案问题

标签:方案,背包,容量,九讲,问题,01,物品
From: https://blog.csdn.net/m0_73633807/article/details/142823862

相关文章

  • 远程桌面方案记录
    远程桌面方案记录随着设备越来越多,各个设备之间的可达性显得尤为重要。我目前已实现基于WireGuard的星型拓扑组建大内网,不过目前对于不支持p2p这一点感觉不太满意,等折腾成功之后再单独写一篇笔记记录。本文则侧重于记录我正在使用的远程桌面方案的优缺点、以及各种踩坑。ToDesk......
  • Rust 在 Android 的编程实践——技术驱动的车云一体化解决方案探索
    Rust在Android的编程实践——技术驱动的车云一体化解决方案探索Greptime车云一体化解决方案颠覆了从前传统的车云协同模式,采用更加低成本、高效率的方案来满足当前的市场需求。其中GreptimeDBEdge作为核心组件,专为车机环境量身打造。本文旨在详尽探讨在Android平台利用......
  • 腾讯云云服务器数据迁移实战方案
    前言我在三年前购买的腾讯云服务器今年过期咯,今年的腾讯云双十一活动也是给力优惠攻略极速观看:刻不容缓腾讯云双十一活动羊毛攻略!!!-腾讯云开发者社区-腾讯云极速通道购买:腾讯云11.11上云拼团Go经过上面的攻略我购买了一个2h4g和4h8g的云服务器,我将Mysql、Redis......
  • 动态规划-背包01问题推理与实践
    动态规划-背包01问题推理与实践背包01问题描述:有storage大小的背包和weights.size()数量的物品,每个物品i对应的物品大小为sizes[i],价值为values[i],在不超过storage大小的情况下,如何装载物品使背包中的values和最大.物品大小:vector<int>sizes;物品价值:vector<int>v......
  • 企业常见的主数据管理挑战及解决方案
    在当今高度数字化的商业环境中,数据已成为企业决策、运营和战略规划的核心。主数据管理(MDM)作为管理核心业务数据的一种方式,帮助企业确保其关键数据在整个组织中保持一致、准确和可信。然而,许多企业在实施主数据管理时面临着各种挑战,这些挑战可能导致数据质量问题,影响决策效率,甚......
  • 性能测试数据模型建模多种方案
    目录基于业务场景的数据建模负载和压力测试数据建模持续性测试数据建模并发测试数据建模峰值测试数据建模数据量测试数据建模可配置参数测试数据建模基础数据准备方案测试数据准备方案执行过程中数据准备方案数据模型的建模主要针对基础数据、测试数据、执行方案,通......
  • 输入法双拼方案哪个好?
    常见的双拼方案有:小鹤双拼、微软双拼、自然码等,智能ABC,拼音加加,紫光双拼,国标双拼,甚至可以自定义方案。本文会简单介绍下各个方案,让读者参考。‍各输入法支持情况有位UP主做了一张图:可以几乎所有输入法都支持微软双拼,此外小鹤双拼和自然码的支持率也很高。‍选择哪一款......
  • 基于51单片机的蓝牙循迹小车 代码方案分享
    一、硬件    包括:            STC89C52RC单片机        sg90舵机(阿克曼转向)        TCRT5000红外模块(黑白线检测)            小车用电机x2(使用L298N电机驱动板驱动)          ......
  • 【主板定制化服务】专业主板定制化服务,全流程覆盖,为客户打造独特硬件方案
    在当今的科技环境中,标准化的硬件产品常常无法满足各种细分领域的特殊需求,尤其是工业控制、嵌入式系统、服务器等场景中,个性化设计的主板能够为用户带来更高的灵活性和性能优化。我们团队专注于主板研发,提供一系列标准产品,同时能够为客户量身定制各种主板解决方案,以满足不同行业......
  • conda与pip安装软件包的代理/换源解决方案
    方案0:终端setproxysethttps_proxy=https://127.0.0.1:7890exporthttps_proxy=https://127.0.0.1:7890查看set|grepproxyecho$https_proxy区别使用set可以设置和查看变量,但不一定使其在子进程中可用。使用export可以将变量导出为环境变量,使其在子进程中可......