Charm Bracelet(01背包)
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 6
1 4
2 6
3 12
2 7
Sample Output
23
题目大意:
给定n个物品,m的最大承重,求在承重范围之内的最大的D的和。
01背包模板
#include <iostream>
#include <algorithm>
using namespace std;
int w[],d[],dp[];
int n,m;
int main()
{
cin>>n>>m;
for(int i=;i<=n;i++)
cin>>w[i]>>d[i];
for(int i=;i<=n;i++)
for(int j=m;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
cout<<dp[m]<<'\n';
return ;
}
最新文章
- JavaScript弹窗
- Labview调用Python脚本
- java 事件监听 - 键盘
- java 22 - 12 多线程之解决线程安全问题的实现方式1
- 浅谈JS继承
- SPSS数据分析—多重线性回归
- 夺命雷公狗ThinkPHP项目之----企业网站17之网站配置页的添加
- android requestWindowFeature使用详解
- (大数据工程师学习路径)第四步 SQL基础课程----select详解
- Saltstack 服务器基本安装
- 第二篇 Flask 中的 Render Redirect HttpResponse
- Openldap命令详解
- Modern Data Lake with Minio : Part 1
- ASP.NET Web API实践系列06, 在ASP.NET MVC 4 基础上增加使用ASP.NET WEB API
- MySQL Crash Course #20# Chapter 28. Managing Security
- 牛客练习赛14A(唯一分解定理)
- 盒子模型之margin相关技巧!
- 前端福利之jQuery文字轮播特效(转)
- Spring_总结_04_高级配置(六)_Bean的初始化和销毁
- python对文件写操作报错UnicodeEncodeError
热门文章
- 使用PlSQLDeveloper工具查询Oracle会话数
- dubbo中Hessian方法重载问题处理
- SpringMVC-核心配置文件spring-mvc.xml
- 18.5.2动态代理和AOP
- pscp多线程传输文件
- PHP在不同页面间传递Json数据示例代码
- MySQL系列:隐式类型转化可能带来的坑
- hihocoder1133 二分&#183;二分查找之k小数
- VS2015调用低版本lib库出现“无法解析的外部符号 __snprintf ”问题的解决
- checkbox:click事件触发文本框显示隐藏