51nod 1085 背包问题
2024-08-27 06:21:47
在N件物品取出若干件放在容量为W的背包里,每件物品的体积为W1,W2……Wn(Wi为整数),与之相对应的价值为P1,P2……Pn(Pi为整数)。求背包能够容纳的最大价值。
收起
输入
第1行,2个整数,N和W中间用空格隔开。N为物品的数量,W为背包的容量。(1 <= N <= 100,1 <= W <= 10000)
第2 - N + 1行,每行2个整数,Wi和Pi,分别是物品的体积和物品的价值。(1 <= Wi, Pi <= 10000)
输出
输出可以容纳的最大价值。
输入样例
3 6
2 5
3 8
4 9
输出样例
14 代码:
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 100
#define DMAX 10000
using namespace std; int N,W;
int w[MAX],p[MAX];
int dp[DMAX + ];
int main() {
scanf("%d%d",&N,&W);
for(int i = ;i < N;i ++) {
scanf("%d%d",&w[i],&p[i]);
}
for(int i = ;i < N;i ++) {
for(int j = W;j >= w[i];j --) {
dp[j] = max(dp[j],dp[j - w[i]] + p[i]);
}
}
printf("%d",dp[W]);
}
最新文章
- Jquery中的bind(),live(),delegate(),on()绑定事件方式
- HTML5新的标签和属性
- 【JSP】Tiles框架的基本使用
- mp3 音频 音乐 tag ID3 ID3V1 ID3V2 标签 读取信息 获得图片 jpeg bmp 图片转换等
- leetCode 48.Rotate Image (旋转图像) 解题思路和方法
- [置顶] Linux协议栈代码阅读笔记(一)
- Ubuntu中nfs服务器安装与配置
- 谈谈事件对象-event
- Mysql了解及安装
- InheritedWidget
- react native webview 不能滑动页面
- SQL Server日志文件过大 大日志文件清理方法 不分离数据库
- python 回溯法 子集树模板 系列 —— 17、找零问题
- Go语言之高级篇beego框架安装与使用
- Python 使用 lambda() 结合sort() 或 sorted() 对列表嵌套字典格式的数据进行排序
- ios开发之修改 UITableview 滚动条颜色的方法
- php-resque 简单的php消息队列
- bzoj 1951 [Sdoi2010]古代猪文 ——数学综合
- P1069 细胞分裂
- J2EE 学习路线
热门文章
- TNS-12541: TNS:no listener , TNS-12542: TNS:address already in use
- Caffe实现多标签输入,添加数据层(data layer)
- 深入理解Java虚拟机(1)--Java内存区域
- LVS+Keepalived+Tomcat实现高可用性及均衡负载
- 解决Spark用Maven编译时报Exception in thread ";main"; java.lang.OutOfMemoryError: PermGen space异常
- windchill相关功能操作
- Node.js 项目的配置文件
- dataframe 列名重新排序
- Pandas系列
- glance cache