POJ 3624 Charm Bracelet (01背包)
题目链接:http://poj.org/problem?id=3624
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 andDi
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 题解:还是01背包模板题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define lowbit(x) (x&(-x))
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
bool cmp(int x,int y)
{
return x>y;
}
const int N=;
const int mod=1e9+;
int dp[N];
int main()
{
std::ios::sync_with_stdio(false);
int n,m,x,y;
mem(dp);
cin>>n>>m;
for(int i=;i<=n;i++){
cin>>x>>y;
for(int j=m;j>=x;j--){
dp[j]=max(dp[j],dp[j-x]+y);
}
}
cout<<dp[m]<<endl;
return ;
}
最新文章
- 411. Minimum Unique Word Abbreviation
- web安全之文件上传漏洞
- Scala.js v0.1 发布,在浏览器直接运行 Scala
- linux下安装编译php的curl扩展
- WEB简单数据操作练习
- noip2007提高组题解
- Java类的生命周期详解
- 你以为PHP那么好自定义升级?
- strlen、strcmp、strcat、strcpy、memcpy基础函数的实现
- pytesseract使用
- Leetcode_168_Excel Sheet Column Title
- 一些常用的js循环,如for
- koa-passport实现本地验证
- LNMP 如何安装mongodb
- Python基础05_str_补充
- js 自定义类Android吐司提示框
- linux内存源码分析 - SLAB分配器概述
- 【IT界的厨子】酱香鲈鱼
- Mybatis抛出 Closing non transactional SqlSession [org.apache.ibatis.session.defaults.DefaultSqlSession@f54509]异常
- jenkins设置CSRF 协议(CRUMB值设置)
热门文章
- finecms5采集接口下载
- 报错解决——OSError: libdarknet.so: cannot open shared object file: No such file or directory
- what&#39; the python之递归函数、二分算法与汉诺塔游戏
- 前端框架之Vue(8)-表单输入绑定
- 小程序编辑器vscode
- OpenVPN简介及架构详解
- 关于spark的mllib学习总结(Java版)
- (转)Fabric 1.0 读写集
- k8s pv 的三种挂载模式
- Amazon RDS 上的 Microsoft SQL Server &#187; 导入和导出 SQL Server 数据库