poj3624背包问题(一维数组)
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
#include <stdio.h> #include <iostream> #include <string.h> using namespace std; #define Maxn 14000 int Val[Maxn]; int bag(int val[],int weight[],int M,int N) { memset(Val,0,sizeof(Val)); int maxn = 0; for(int i = 1; i <= N; i++) { for(int j = M; j >= weight[i]; j--) { if (Val[j] < (Val[j - weight[i]] + val[i])) { Val[j] = max(Val[j],Val[j - weight[i]] + val[i]); } } } return Val[M]; } int main() { int N,M; int val[Maxn]; int weight[Maxn]; scanf("%d%d",&N,&M); for(int i = 1; i <= N; i++) { scanf("%d",weight+i); scanf("%d",val+i); } printf("%d\n",bag(val,weight,M,N)); return 0; }
最新文章
- Jmeter测试环境搭建(一)
- IOS5中的Safari不兼容Javascript中的Date问题
- 仿微信朋友圈图片查看-glide加载网络图片,photoview 实现缩放
- Windows7下Blend for Visual Studio 2012使用问题
- PHP学习(二)----数组
- MySQL数据库表中有usage字段名后的后果
- Xcode中使用插件
- VS下 dllimport与dllexport作用与区别
- CentOS 7.0 systemd代替service
- Oracle EBS-SQL (PO-9):检查期间采购订单执行情况.sql
- Caffe安装过程错误处理方法
- 12C 连接方式和 Oracle Easy Connect Naming method
- 读书笔记之JavaScript中的数据类型(1)
- Spring切面编程步骤
- CSS3_过渡_2D 变换_瓶体旋转_动态时钟
- Target JRE version (1.7.0_79) does not match project JDK version (java version ";1.8.0_171";), will use sources from JDK: 1.7
- cmd Telnet 手工模拟http请求
- Springboot集成ES启动报错
- UML类图及类与类之间的关系
- 项目报错:Caused by: java.lang.ClassNotFoundException: Didn&#39;t find class ";...";on path: DexPathList