（C语言动态规划算法）0/1背包问题_动态规划0-1背包问题c语言-程序员宅基地

技术标签： 算法  c++  c语言  蓝桥杯  动态规划  

  Description

已知一个载重为M的背包和n件物品，物品编号从0到n-1。第i件物品的重量为 wi，若将第i种物品装入背包将获益pi，这里，wi>0，pi>0，0<=i<n。所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。

Input

第 1 行中有 2 个正整数 n（n<=50）和M ，表示有 n件物品，背包载重为M(m<=100)。然后输入n个物品的重量，最后输入n个物品的收益值。

Output

最佳装载方案的总收益

Sample Input

3 6
2 3 4
1 2 4

Sample Output

5
方法：将规模大的问题转化为小问题。
过程：从第一个开始选，选出最优解，依次类推，求出第n个相应的最优解。
        
        
#include<stdio.h>

int max(int a,int b){
       return a>b?a:b;
}
int main()
{
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    int w[n],p[n],f[200000]={0};
    for(i=0;i<n;i++) scanf("%d",&w[i]);
    for(i=0;i<n;i++) scanf("%d",&p[i]);
    
    for(i=0;i<n;i++){
    for(j=m;j>=1;j--){
    if(j>=w[i]) f[j]=max(f[j],f[j-w[i]]+p[i]);
    }
    }
    printf("%d",f[m]);
    return 0;
}

这里，我们举个列子，取n=3,M=3;（此处数据取小一点，便于理解）
        每个物体重量分别为1 2 1
        每个物体收益分别为3 4 5 
        f[W]是我们最后要求的答案，先把数组f全赋值为0，代表初始利润是0；
我们以i=0时做第一次循环得出相应结果为（j认为是背包中剩余可装重量)

 不难发现，在只对第一个物体进行选择时，不同背包容量都做出了最优选择。

接下来在进行i=1时的第二次循环,结果为：

 此处没有f[1]是因为1小于第二个物体重量。

i=2，最后一次循环结果为：

 程序结束，这个程序是求了不同背包容量时对第1、2........n个物体选择时所求的最优解，既然每一小部分都是最优解。那加起来合为一个整体也一定为最优解，如最后一张图片，当背包容量为3时，最优解为9。当背包容量为2时，最优解为8。当背包容量为3时，最优解为5。但我们只需求背包容量为3时的最优解，所以输出f[3],即f[m].
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_61832536/article/details/122277583

智能推荐

离线安装htop工具_htop 离线-程序员宅基地

文章浏览阅读4.8k次。htop众所周知是是一款强大的是Linux系统中的一个互动的进程查看器（作为top的替代品），一个文本模式的应用程序(在控制台或者X终端中)，一般情况下一句yum install htop就能轻松安装，但是很多时候我们会遇到无法连接外网的情况。_htop 离线

Task1 随机事件与随机变量_如何在task里随机一个变量-程序员宅基地

文章浏览阅读214次。随机事件与随机变量基本概念随机现象： 现实生活中，一个动作或一件事情，在一定条件下，所得的结果不能预先完全确定，而只能确定是多种可能结果中的一种。样本空间：一个试验所有可能的集合。样本点：试验的每一种可能的结果。随机事件：样本空间满足一定条件的子集。概率定义：每个事件AAA，定义一个实数P(A)P(A)P(A)与之对应，若函数。概率公理：非负性：0<P(A)<=10<P(A)<=10<P(A)<=1;可加性：若事件A1,A2,A3,...A_1,A__如何在task里随机一个变量

开机提示：error:no such partition grub rescue>-程序员宅基地

文章浏览阅读273次。原来电脑装的是win7和ubuntu双系统，后来配置java环境的时候把ubuntu给整残了，就在win7下把ubuntu的分区给删除了，没想到重启的时候直接就显示error:no such partition grub rescue> 具体原因是什么网上说的都很清楚（删除系统后，grub的配置文件没了，而mbr没有改回来，所以出现这种状况），解决方案也有几个，总..._开机显示error:nosuch partition entering rescue mode...

【数据分析】基于RFM模型的线上零售中的客户细分（二）：RFM模型实战_零售数据模型有哪些-程序员宅基地

文章浏览阅读3.9k次，点赞14次，收藏59次。这篇博客将会结合具体的商业实例介绍同期群分析、RFM模型，并利用K-Means聚类算法在RFM模型上找到合适的细分集群。_零售数据模型有哪些

阿里云ECS服务器 因用户激增导致服务器崩溃，优化实操过程_服务器人数过多崩溃-程序员宅基地

文章浏览阅读1.2k次。因为公众号搞了一波裂变活动，瞬间来了一大波用户，导致我的网站、小程序、公众号回复全面崩溃，难受！遇到这种问题第一反应是：1、升级服务器的带宽于是花了点钱将带宽从3M到5M，刚开始有点效果，但是因为用户太多了，1分钟来1万条消息，带宽升级毕竟太贵了。治标不治本。2、给服务加CDN因为网站需要给公众号返回消息，改成CDN后消息不对，所以这个方法对我不适用，只能找其他方法优化了。3、给图片加OSS存储因为看小程序的图片一张都是300kb左右，整个页面就是1M..._服务器人数过多崩溃

Android 应用程序组件_android清单文件包含了组成应用程序模块所需要的组件-程序员宅基地

文章浏览阅读168次。应用程序组件是一个Android应用程序的基本构建块。这些组件由应用清单文件松耦合的组织。AndroidManifest.xml描述了应用程序的每个组件，以及他们如何交互。以下是可以在Android应用程序中使用的四个主要组件。组件 描述 Activities 描述UI，并且处理用户与机器屏幕的交互。 Services 处理与应用程序关联的后台操作。 Broadcast Receivers 处理Android操作系统和应用程序之间的通信。 Content Prov_android清单文件包含了组成应用程序模块所需要的组件

随便推点

将 PDF 转换为矢量图 emf_pdf转emf-程序员宅基地

文章浏览阅读2w次，点赞15次，收藏43次。此篇博客介绍了一种将PDF转换为矢量图emf、编辑emf的方法（需要Adobe Acrobat）_pdf转emf

各个 Android Gradle 插件版本所需的 Gradle 版本_gradle distributionurl 有那些版本-程序员宅基地

文章浏览阅读1.1k次。下表列出了各个 Android Gradle 插件版本所需的 Gradle 版本。要获得最佳性能，您应该使用 Gradle 和插件这两者的最新版本。插件版本 所需的 Gradle 版本 1.0.0 - 1.1.3 2.2.1 - 2.3 1.2.0 - 1.3.1 2.2.1 - 2.9 1.5.0 2.2.1 - 2.13 2.0.0 - 2.1...._gradle distributionurl 有那些版本

esp32 mqtt协议上报 dht11温湿度数据到onenet 指令下发控制开关灯_esp32连接onenet控制灯开关-程序员宅基地

文章浏览阅读1.9k次。一直没有时间玩esp32开发板，网上说这款板子性能强悍，双cpu，支持蓝牙.....等等，优点就不说了，自行百度吧。抽了一个星期时间，用esp32做了一款小项目，和大多数物联网项目一样，具有基本的数据上报，指令下发功能。如下图，我用它来开关灯实现步骤：1、先在arduino上装好esp32的开发环境，这个网上已经有很多了，我就不再写了。2、当然是写代码，下载mqtt类库。3、我因为太穷，所以就用onenet来当服务器吧，那就去onenet开个户，建好产品、设备。4、写上位_esp32连接onenet控制灯开关

navicat怎么查看mysql版本_navicat怎么看版本-程序员宅基地

文章浏览阅读1.3w次。navicat是一款桌面级的数据库管理器，支持 Win、macOS 和 linux，非常强大，知名度十分高。支持 MySQL、MariaDB、SQL Server、SQLite、Oracle 和 PostgreSQL 的数据库等数据库。下面为大家介绍一下，navicat查看版本信息的方法方法一1、这里不介绍navicat的安装，我们打开navicat软件，最上的标签栏点击‘帮助’按钮。2、会有弹出..._navicat查看mysql版本

idea 注释插件_开发效率不高？墙裂推荐这十款精选IntelliJ Idea插件-程序员宅基地

文章浏览阅读3.3k次。(给程序员零距离加星标，了解项目开发.)作者|雷架来源 |爱笑的架构师(ID：DancingOnYourCode)俗话说：＂工欲善其事必先利其器＂，小主从项目实战的角度在众多的idea插件中挑选了10款开发必备的神器，帮助大家在日常编码中提升开发效率。1Key Promoter X实用指数：★★★★★装逼指数：★你还在为记不住快捷键烦恼吗，Key Promoter X可以帮助你快..._idea@value寻找注释插件

mybatis看这一篇就够了，简单全面一发入魂_mybatis一发入魂-程序员宅基地

文章浏览阅读10w+次，点赞1.9k次，收藏1.3w次。文章目录Mybatis概述快速入门原生开发示例基于Mapper代理的示例基于注解的示例应用场景主键返回批量查询动态SQL缓存关联查询延迟加载逆向工程PageHelper分页插件Mybatis PlusMybatis概述mybatis是什么？有什么特点？它是一款半自动的ORM持久层框架，具有较高的SQL灵活性，支持高级映射(一对一，一对多)，动态SQL，延迟加载和缓存等特性，但它的数据库无关性较低什么是ORM？Object Relation Mapping，对象关系映射。对象指的是Java_mybatis一发入魂

推荐文章

热门文章

相关标签