【模板】51Nod--1085 01背包
2024-08-24 19:34:05
在N件物品取出若干件放在容量为W的背包里,每件物品的体积为W1,W2……Wn(Wi为整数),与之相对应的价值为P1,P2……Pn(Pi为整数)。求背包能够容纳的最大价值。
Input
第1行,2个整数,N和W中间用空格隔开。N为物品的数量,W为背包的容量。(1 <= N <= 100,1 <= W <= 10000)
第2 - N + 1行,每行2个整数,Wi和Pi,分别是物品的体积和物品的价值。(1 <= Wi, Pi <= 10000)
Output
输出可以容纳的最大价值。
Input示例
3 6
2 5
3 8
4 9
Output示例
14
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[+];
int w[],p[];
int main()
{
int N,W;
scanf("%d %d",&N,&W);
for(int i=;i<N;i++)
scanf("%d %d",&w[i],&p[i]);
for(int i=;i<=W;i++)
dp[i]=;
for(int i=0;i<=N;i++) //核心代码 一维
15 {
16 for(int j=W;j>=w[i];j--)
17 {
18 dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
19 }
20 }
printf("%d\n",dp[W]); return ;
}
最新文章
- 端口扫描base
- SQL2008关于quotename的用法
- swift学习笔记之-函数
- oracle group 语句探究(笔记)
- hdu 3790 最短路径问题(两个限制条件的最短路)
- 如何在webstrom中配置eslint和less
- CSS-边框-效果
- HDU 1722 Cake
- C# new关键字和对象类型转换(双括号、is操作符、as操作符)
- WPF Uri
- laravel服务容器
- python字符串,列表常用操作
- dict使用
- centos 7 下多网卡绑定+ vlan 网卡配置
- php中&;运算符的理解与使用
- Datatables跳转到指定页
- 2016-2017-2 20155302 实验四 Android 开发基础
- TortoiseSVN教程
- Unity5.x在mac下的破解
- Elementui 导航组件和Vuejs路由结合
热门文章
- CSS active选择器与CSS hover选择器
- eclipse中Build Path 导入的包和复制到 lib 包的区别
- ECMAScript 6 中的快捷语法汇总及代码示例
- PHP实现简单的评论与回复功能还有删除信息
- Angular 4 学习笔记 从入门到实战 打造在线竞拍网站 基础知识 快速入门 个人感悟
- CSS input type=";number";出现上下箭头时解决方案
- eclipse更改maven的本地路径和外部仓库地址
- H5仿微信界面教程(一)
- Error creating document instance
- MySQL存储写入性能严重抖动分析