【背包/递推】01背包-白红宇的个人博客

【背包/递推】01背包

发布日期：2021-05-07 22:48:04 浏览次数：17 分类：精选文章

本文共 392 字，大约阅读时间需要 1 分钟。

题目

经典啊。。。

输入

第1行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；

第2至N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

输出

仅一行，一个数，表示最大总价值。

思路

用个数组k表示当空间=j时，最大价值。如果k[j]放得下此物品，比较k[j]和k[j-空间]，赋值。

然后输出k[m]。

代码

#include
   
    int m,n,i,j,k[201]={   0},a,z;int main(){       scanf("%d%d",&m,&n);	for(i=1;i<=n;i++){   		scanf("%d%d",&a,&z);		for(j=m;j>=a;j--)    		    if(k[j-a]+z>k[j])		    k[j]=k[j-a]+z;	}	printf("%d",k[m]);}

上一篇：【DP】传球游戏

下一篇：【DP】糖果盒

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

推荐文章

两款用于检测内存泄漏的软件 2019-03-04

王爽《汇编语言》读书笔记三寄存器（内存访问） 2019-03-04

IDEA出现问题：Received fatal alert: protocol_version 解决方案 2019-03-04

IDEA 热部署太热情不好（失去焦点就热部署） 2019-03-04

访问docker中的nginx容器部署 2019-03-04

Airtest自动化测试 Docs airtest.core.android package 2019-03-04

SVN Unable to connect to a repository at URL 的解决方案 2019-03-04

准确率94%！Python 机器学习识别微博或推特机器人 2019-03-05

Android基本知识 2019-03-05

在Java中，return null 是否安全，为什么？ 2019-03-05

命令模式【Command Pattern】 2019-03-05

如何将自己写的代码编进系统 2019-03-05

OSI 7 层网络模型 2019-03-05

Spring Bean 生命周期 2019-03-05

JDK 内置线程池 2019-03-05

JVM 参数默认值查询 2019-03-05

SVN 和 Git 区别 2019-03-05

JDK 内置的多线程协作工具类的使用场景 2019-03-05

Java 源代码到运行的过程 2019-03-05

Java 中哪些对象可以获取类对象 2019-03-05

白红宇的个人博客 - 记录点点滴滴的事 - 您是第 457225773 位访客

题目

输入

输出

思路

代码

发表评论

最新留言

关于作者

推荐文章