Charm Bracelet-POJ3624(01背包)
http://poj.org/problem?id=3624
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 29444 | Accepted: 13198 |
Description
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 这个是简单的01背包 从我开始接触到背包到现在我还是不懂背包的原理
开始背包的旅程
正常的背包是
i 1....n
j m....0
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
但是这个范围较大
如果用二维的会超内存
可以转化成一维的
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream> using namespace std; #define N 3500
int dp[]; int main()
{
int n,m,w[N],v[N];
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i=;i<=n;i++)
scanf("%d %d",&w[i],&v[i]);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
{
for(int j=m;j>=;j--)
{
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
printf("%d\n",dp[m]);
}
return ;
}
最新文章
- linux内核中的每cpu变量
- 使用天天模拟器开发Android应用
- matlab global 不能传向量/矩阵
- android中View的GONE和INVISIBLE的原理
- 在命令行中通过adb shell am broadcast发送广播通知
- 用c#开发微信 (21) 微信酒店预订系统
- win8找到程序员计算器
- Mmap的实现原理和应用
- Linux IP 路由实现
- Java基础巩固----泛型
- BZOJ 1269: [AHOI2006]文本编辑器editor( splay )
- Android中Menu的基本使用方法
- 1441: Min
- 【PHP】this,self,parent的区别(转)
- C语言之找零钱
- shiro权限控制(二):分布式架构中shiro的实现
- Springboot项目如何把项目运行在服务器上
- Linux~学习笔记目录索引
- 使用ionic2开发一个二维码扫描功能
- python制作模块
热门文章
- listBox 搜索左右移动
- Android ImageView setImageBitmap 不显示图片
- Java线程-线程、程序、进程的基本概念
- provider模式
- SceneAction$$FastClassByCGLIB$$7330f7b9.invoke(int, Object, Object[]) line: not available
- VS2015 update3 安装 asp.net core 失败
- (转)hibernate-5.0.7+struts-2.3.24+spring-4.2.4三大框架整合
- Okhttp3发送xml、json、文件的请求方法
- js 上传图片、压缩、旋转
- iOS 导航栏风格