1)0-1背包问题和 零碎背包问题是不同的,前者只能用动态规划来做, 后者可以用贪心算法。
2)动态规划的核心是 “有多个重叠子问题”,“自底向上”解决问题。
3) 0-1背包问题 ,W为最大重量,n为物体个数,求最大的价值Value,可在O(nW)的时间复杂度内解算出来。
Language:Default
Charm Bracelet
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 10014
Accepted: 4498
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 theN (1 ≤
N ≤ 3,402) available charms. Each charm i in the supplied list has a weightWi (1 ≤
Wi ≤ 400), a 'desirability' factorDi (1 ≤
Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more thanM (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
Source
USACO 2007 December Silver
分享到:
相关推荐
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ初级-动态规划 解题报告+AC代码
不错的资源 收集了网上的一些解题报告 方便同学们学习参考
北大POJ2002-Squares 解题报告+AC代码
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
算法-开关问题(POJ-1830)(包含源程序).rar
北大POJ初级题-数据结构:解题报告+AC代码
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
算法-炮兵阵地(POJ-1185)(包含源程序).rar
北大POJ初级-所有题目AC代码+解题报告
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
<1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 双背包求最优值 构造三角形问题 带上下界限制的背包问题(012背包) 3.线性的动态规划问题 <1>积木游戏...
北大POJ3299-Humidex 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ3414-Pots 解题报告+AC代码
POJ水题集-----50道左右-----增加自信啊..
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告