(dp专题006)hdu 2602 Bone Collector(01背包)

题目链接

题意:容量为V的背包,n个骨头,给出价值和体积,问最多能装多少价值的背包。

思路:01背包裸体。

 

[dp专题005]hdu 1864最大报销额(01背包,垃圾题)

hdu1864题目链接

题意:中文题目,不多说了。

思路:正解是01背包,呵呵呵。

出题人是傻逼吗?

不给数据范围?

以及,正解的01背包基于所有的发票额度的只有2位小数。这是让人猜?

本来看到这题这么恶心时不打算写的…

写了的原因纯粹是为了吐槽傻逼出题人..

简直是我做得最垃圾的题目之一。

 

 

(dp专题004)hdu 2955Robberies(01背包变形)

题目链接

题意: 给出n个银行 ,以及抢劫每个银行可以得到的价值和被抓的概率,不同银行之间被抓的概率是相互独立的,现在给出安全概率p,只有当概率从小于安全概率时才是安全的,问最多能抢劫多少价值。

思路:一开始很直接就想到把概率算成容量,

于是就成了经典的01背包,然后发现概率是double型。。。想当然得以为最多是2位小数,于是都*100转化成了整数做01背包。

然而正确思路是,把银行价值看成背包容量,而背包价值是概率!

将危险的概率转化成安全概率(1-危险概率=安全概率)

然后做01背包。

然后从大到小扫一遍价值,第一个大于安全概率的就是答案。

注意精度。

 

BZOJ 3407: [Usaco2009 Oct]Bessie’s Weight Problem 贝茜的体重问题(01背包)

3407: [Usaco2009 Oct]Bessie’s Weight Problem 贝茜的体重问题

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 88  Solved: 79
[Submit][Status][Discuss]

Description

贝茜像她的诸多姊妹一样,因为从约翰的草地吃了太多美味的草而长出了太多的赘肉.所以约翰将她置于一个及其严格的节食计划之中.她每天不能吃多过H(5≤日≤45000)公斤的干草.贝茜只能吃一整捆干草;当她开始吃一捆干草的之后就再也停不下来了.她有一个完整

的N(1≤N≤500)捆可以给她当作晚餐的干草的清单.她自然想要尽量吃到更多的干草.很自然地,每捆干草只能被吃一次(即使在列表中相同的重量可能出现2次,但是这表示的是两捆干草,其中每捆干草最多只能被吃掉一次).

给定一个列表表示每捆干草的重量Si(1≤Si≤H),求贝茜不超过节食的限制的前提下可以吃掉多少干草(注意一旦她开始吃一捆干草就会把那一捆干草全部吃完).

Input

第1行:两个由空格隔开的整数日和N.

第2到第N+1行:第i+l行是一个单独的整数,表示第i捆干草的重量Si.

Output

 

一个单独的整数表示贝茜在限制范围内最多可以吃多少公斤的干草.

Sample Input

56 4
15
19
20
21

Sample Output

56

HINT

有四捆草,重量分别是15,19,20和21.贝茜在56公斤的限制范围内想要吃多少就可以吃多少.

贝茜可以吃3捆干草(重量分别为15,20,21).恰好达到她的56公斤的限制.

 

 

 

BZOJ 1649: [Usaco2006 Dec]Cow Roller Coaster (dp,类似01背包)

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 504  Solved: 265
[Submit][Status][Discuss]

Description

The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 <= L <= 1,000). The roller coaster comprises a collection of some of the N (1 <= N <= 10,000) different interchangable components. Each component i has a fixed length Wi (1 <= Wi <= L). Due to varying terrain, each component i can be only built starting at location Xi (0 <= Xi <= L-Wi). The cows want to string together various roller coaster components starting at 0 and ending at L so that the end of each component (except the last) is the start of the next component. Each component i has a “fun rating” Fi (1 <= Fi <= 1,000,000) and a cost Ci (1 <= Ci <= 1000). The total fun of the roller coster is the sum of the fun from each component used; the total cost is likewise the sum of the costs of each component used. The cows’ total budget is B (1 <= B <= 1000). Help the cows determine the most fun roller coaster that they can build with their budget.

奶牛们正打算造一条过山车轨道.她们希望你帮忙,找出最有趣,但又符合预算的方案.  过山车的轨道由若干钢轨首尾相连,由x=0处一直延伸到X=L(1≤L≤1000)处.现有N(1≤N≤10000)根钢轨,每根钢轨的起点Xi(0≤Xi≤L- Wi),长度wi(l≤Wi≤L),有趣指数Fi(1≤Fi≤1000000),成本Ci(l≤Ci≤1000)均己知.请确定一种最优方案,使得选用的钢轨的有趣指数之和最大,同时成本之和不超过B(1≤B≤1000).

Input

* Line 1: Three space-separated integers: L, N and B.

* Lines 2..N+1: Line i+1 contains four space-separated integers, respectively: Xi, Wi, Fi, and Ci.

    第1行输入L,N,B,接下来N行,每行四个整数Xi,wi,Fi,Ci.

Output

* Line 1: A single integer that is the maximum fun value that a roller-coaster can have while staying within the budget and meeting all the other constraints. If it is not possible to build a roller-coaster within budget, output -1.

Sample Input

5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2
 

Sample Output

17
选用第3条,第5条和第6条钢轨
思路:一个类似01dp的背包
dp[i][j]表示长度为i,成本为j的最大有趣指数。
这个想到了。。
然后转移没有推出来。。。
因为潜意识里总觉得循环的变量是要和dp数组的两维一致。。。
实际上根本无关好吗23333
初始化数组dp为-1,dp[0][0]=0
为-1是因为无解输出-1,这样就不用特别处理了。。。
转移方程为:f[i][end[a]]=max{f[i-cost[a][begin[a]]+w[a]} 当f[i-cost[a][begin[a]]可行时
参考了这篇题解:

bzoj1649题解

 

 

codeforces #319 B – Modulo Sum (抽屉原理,dp)

背包还是理解的不够透彻..

因为每次都是用那个一维形式的.

这道题的做法类似01背包.

此外还可以有一个优化…

当n>m的时候...根绝抽屉原理..一定为yes..

复杂度可以从o(nm)优到 o(m^2)

hdu 1171 Big Event in HDU (母函数,01背包)

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26534    Accepted Submission(s): 9332

Problem Description
Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don’t know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

 

Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 — the total number of different facilities). The next N lines contain an integer V (0<V<=50 –value of facility) and an integer M (0<M<=100 –corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.

 

Output
For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.

 

Sample Input
2
10 1
20 1
3
10 1
20 2
30 1
-1

 

Sample Output
20 10
40 40

 

Author
lcy

背包。

所有的设备不是放在第一部分,就是要放在第二部分。

那么对于第一部分,或者第二部分,每一个设备就只有放和不放两种情况。

然后感觉就是做一个容量为总数的一半的01背包

然后脑抽看到第一部分可以大于一半,觉得这么想是错的。。。

实际上并不是,因为第二部分总要比第一部分小,所以第二部分是不可能大于一半的。

所以我们对于第二部分做01背包。

 

 

 

还有一种母函数的做法:先得到每种价值有多种种方法,然后从总价值一半向下找到第一个方案数非0的价值,就是答案。
注意。。。数组开小不一定是re…tle,wa,re都有可能

注意。。。数组开小不一定是re…tle,wa,re都有可能

注意。。。数组开小不一定是re…tle,wa,re都有可能

 

 

 

hdu 1203 I NEED A OFFER! (01背包)

I NEED A OFFER!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18287    Accepted Submission(s): 7320

Problem Description
Speakless很早就想出国,现在他已经考完了所有需要的考试,准备了所有要准备的材料,于是,便需要去申请学校了。要申请国外的任何大学,你都要交纳一定的申请费用,这可是很惊人的。Speakless没有多少钱,总共只攒了n万美元。他将在m个学校中选择若干的(当然要在他的经济承受范围内)。每个学校都有不同的申请费用a(万美元),并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”,他大叫一声。帮帮这个可怜的人吧,帮助他计算一下,他可以收到至少一份offer的最大概率。(如果Speakless选择了多个学校,得到任意一个学校的offer都可以)。

 

Input
输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000)
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。

 

Output
每组数据都对应一个输出,表示Speakless可能得到至少一份offer的最大概率。用百分数表示,精确到小数点后一位。

 

Sample Input
10 3
4 0.1
4 0.2
5 0.3
0 0

 

Sample Output

44.0%

Hint

You should use printf(“%%”) to print a ‘%’.

 

Author
Speakless

 

Source

 

Recommend
JGShining   |   We have carefully selected several similar problems for you:  1171 2159 2955 1176 1114
01背包
最开始WA在初始化,dp数组全都赋值为1,忘赋了dp[0],导致如果恰好是花光所有钱得到答案的时候答案错误。
然后还一直WA。
后来发现是当N=0的时候,我直接取了所有A[I]=0对应的B[I]中最大的值。。。这显然是错的,少年你是脑抽吗。。。。。
然后修改了下,终于A掉了。。。。。

hdu 2546 饭卡 (01背包)

饭卡

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14225    Accepted Submission(s): 4945

Problem Description
电子科大本部食堂的饭卡有一种很诡异的设计,即在购买之前判断余额。如果购买一个商品之前,卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的余额最少。
某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。
 

 

Input
多组数据。对于每组数据:
第一行为正整数n,表示菜的数量。n<=1000。
第二行包括n个正整数,表示每种菜的价格。价格不超过50。
第三行包括一个正整数m,表示卡上的余额。m<=1000。 n=0表示数据结束。
 

 

Output
对于每组输入,输出一行,包含一个整数,表示卡上可能的最小余额。
 

 

Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
 

 

Sample Output
-45
32
 

 

Source
 
 
 
在入门dp。
显然是01背包。 cost和value都是价钱。
但是有限制条件。
很容易想到,为了使得余额最少,我们要把最贵的留在最后买。
读入的时候把最贵的菜价拿出来
然后剩下的n-1个菜,做一个容量为m-5的01背包。
注意如果m<5,直接输出即可。