背包问题类型各题总结acm.docx
《背包问题类型各题总结acm.docx》由会员分享，可在线阅读，更多相关《背包问题类型各题总结acm.docx（52页珍藏版）》请在冰点文库上搜索。
背包问题类型各题总结acm
分组背包：
ProblemC:
超市购物
TimeLimit:
1Sec MemoryLimit:
128MB
SUBMIT:
21 Solved:
10
[SUBMIT][STATUS]
Description
上次去超市扫荡回来的东西用完了,Staginner又得跑超市一趟，出发前他列了一张购物清单，打算去买K种不同的商品,每种买一件。
到了超市，Staginner发现每种商品有N个品牌，每个品牌此商品的价格为Vi，对Staginner的作用值为Wi，他会从这N个品牌里面挑一个品牌买。
这时，Staginner突然想起出门时只带了M元钱，又懒得去取钱了，所以不一定能买完K种商品，只好尽可能地让买的东西对自己的总作用值ans最大。
Input
多组样例。
第一行两个整数K，M代表Staginner想买的不同种类商品的数目和他带的钱（0 以下输入分为K个部分，代表K种商品。
每个部分第一行为一个数字N，代表第k种商品的N个品牌,N不大于10。
之后跟着N行，每行两个数字，代表物品的价格Vi和作用值Wi。
其中0Output
输出Case#:
最大总作用值，每两个样例之间有一个空行。
SampleInput
3100
3
50600
20700
30800
2
30500
40600
1
60200
2500
2
2001000
2601200
1
280300
SampleOutput
Case1:
1400
Case2:
1300
HINT
#include
#include
intbag[100][100],dp[2500],val[100][100];
intmain（）
{
intk,m,n,i,j,t,cnt=0;
while（scanf（"%d%d",&t,&m）!
=EOF）
{
memset（dp,0,sizeof（dp））;
memset（val,0,sizeof（val））;
memset（bag,0,sizeof（bag））;
for（i=0;i {
scanf（"%d",&n）;
bag[i][0]=n;
for（j=1;j<=n;j++）
scanf（"%d%d",&bag[i][j],&val[i][j]）;
}
for（i=0;i for（j=m;j>=0;j--）
for（k=1;k<=bag[i][0];++k）
if（bag[i][k]<=j）
dp[j]=dp[j]>（dp[j-bag[i][k]]+val[i][k]）?
dp[j]:
（dp[j-bag[i][k]]+val[i][k]）;
printf（"Case%d:
%d\n",++cnt,dp[m]）;
printf（"\n"）;
}
return0;
}
Robberies
TimeLimit:
2000/1000MS（Java/Others） MemoryLimit:
32768/32768K（Java/Others）
TotalSubmission（s）:
3802 AcceptedSubmission（s）:
1433
ProblemDescription
TheaspiringRoytheRobberhasseenalotofAmericanmovies,andknowsthatthebadguysusuallygetscaughtintheend,oftenbecausetheybecometoogreedy.Hehasdecidedtoworkinthelucrativebusinessofbankrobberyonlyforashortwhile,beforeretiringtoacomfortablejobatauniversity.
Forafewmonthsnow,Royhasbeenassessingthesecurityofvariousbanksandtheamountofcashtheyhold.Hewantstomakeacalculatedrisk,andgrabasmuchmoneyaspossible.
Hismother,Ola,hasdecideduponatolerableprobabilityofgettingcaught.Shefeelsthatheissafeenoughifthebanksherobstogethergiveaprobabilitylessthanthis.
Input
ThefirstlineofinputgivesT,thenumberofcases.Foreachscenario,thefirstlineofinputgivesafloatingpointnumberP,theprobabilityRoyneedstobebelow,andanintegerN,thenumberofbankshehasplansfor.ThenfollowNlines,wherelinejgivesanintegerMjandafloatingpointnumberPj.
BankjcontainsMjmillions,andtheprobabilityofgettingcaughtfromrobbingitisPj.
Output
Foreachtestcase,outputalinewiththemaximumnumberofmillionshecanexpecttogetwhiletheprobabilityofgettingcaughtislessthanthelimitset.
NotesandConstraints
00.0<=P<=1.0
000.0<=Pj<=1.0
Abankgoesbankruptifitisrobbed,andyoumayassumethatallprobabilitiesareindependentasthepolicehaveverylowfunds.
SampleInput
3
0.043
10.02
20.03
30.05
0.063
20.03
20.03
30.05
0.103
10.03
20.02
30.05
SampleOutput
2
4
6
题意：
输入一个数表示一共多少组数据输入一个浮点型数表示小偷被抓的几率不超过这个情况下能偷的最多钱输入一个整形表示多少个银行
输入3组数据一组2个数分别是该银行的钱以及被抓的几率
求小偷不被抓的情况下能偷的最多钱
思路：
一开始我是让几率当背包然后钱做val但是这样是错误的因为几率是浮点型虽然可以*100变成整形但是几率是相乘得出的而几率当背包无法模拟几率的相乘由题中数据看仿佛用几率当背包然后几率相加能得到样例中的结果但是这是错误的思想
几率哪有加的啊
所以就要变通一下把钱当背包看总共多少钱把几率当背包
#include
#include
doubleval[105],x;
intwei[105];
doublebag[10500000];
void_01bag（intv,intm）
{
inti,j;
for（i=0;i bag[i]=0;
bag[0]=1;
for（i=0;i for（j=v;j>=wei[i];j--）
if（bag[j] bag[j]=bag[j-wei[i]]*（1-val[i]）;
for（i=v;i>=0;i--）
if（bag[i]>=1-x）{printf（"%d\n",i）;break;}
return;
}
intmain（）
{
intt,i,m,v;
scanf（"%d",&t）;
while（t--）
{
v=0;
scanf（"%lf%d",&x,&m）;
for（i=0;i {
scanf（"%d%lf",&wei[i],&val[i]）;
v=v+wei[i];
}
_01bag（v,m）;
}
return0;
}
INEEDAOFFER!
TimeLimit:
2000/1000MS（Java/Others） MemoryLimit:
65536/32768K（Java/Others）
TotalSubmission（s）:
8472 AcceptedSubmission（s）:
3083
ProblemDescription
Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。
要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。
Speakless没有多少钱，总共只攒了n万美元。
他将在m个学校中选择若干的（当然要在他的经济承受范围内）。
每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。
不同学校之间是否得到offer不会互相影响。
“INEEDAOFFER”，他大叫一声。
帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。
（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。
Input
输入有若干组数据，每组数据的第一行有两个正整数n,m（0<=n<=10000,0<=m<=1000）
后面的m行，每行都有两个数据ai（整型）,bi（实型）分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。
Output
每组数据都对应一个输出，表示Speakless可能得到至少一份offer的最大概率。
用百分数表示，精确到小数点后一位。
SampleInput
103
40.1
40.2
50.3
00
SampleOutput
44.0%
Hint
Youshoulduseprintf（"%%"）toprinta'%'.
只要把大于号写成小于号就哦可了
#include
doublebag[10005];
double val[1005];
intwei[1005];
double_01bag（intv,intm）
{
inti,j;
for（i=0;i bag[i]=1.0;
for（i=0;i for（j=v;j>=wei[i];j--）
if（bag[j]>bag[j-wei[i]]*val[i]）
bag[j]=bag[j-wei[i]]*val[i];
returnbag[v];
}
intmain（）
{
intn,m,i;
doubley;
while（scanf（"%d%d",&n,&m））
{
if（m==0&&n==0）break;
for（i=0;i {
scanf（"%d%lf",&wei[i],&y）;
val[i]=1-y;
}
y=1-_01bag（n,m）;
y=y*100;
printf（"%.1lf%%\n",y）;
}
return0;
}
多重背包hdu2191
Input
输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m（1<=n<=100,1<=m<=100）,分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c（1<=p<=20,1<=h<=200,1<=c<=20），分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
Output
对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。
每个实例的输出占一行。
SampleInput
1
82
21004
41002
SampleOutput
400
Author
lcy
#include
#include
intval[5000],wei[5000];
intn;
intbag[105];
int_01bag（intm）
{
inti,j;
memset（bag,0,sizeof（bag））;
for（i=0;i for（j=n;j>=val[i];j--）
if（bag[j] bag[j]=bag[j-val[i]]+wei[i];
returnbag[n];
}
intmain（）
{
intm,t,i,j,ge,temp,v,w;
scanf（"%d",&t）;
while（t--）
{
scanf（"%d%d",&n,&m）;
j=0;
for（i=0;i {
scanf（"%d%d%d",&v,&w,&ge）;
temp=1;
while（ge>temp）//二进制优化
{
val[j]=temp*v;
wei[j++]=temp*w;
ge=ge-temp;
temp=temp*2;
}
val[j]=ge*v;
wei[j++]=ge*w;
}
printf（"%d\n",_01bag（j））;
}
return0;
}
二维背包hdu2159——很重要啊
FATE
TimeLimit:
2000/1000MS（Java/Others） MemoryLimit:
32768/32768K（Java/Others）
TotalSubmission（s）:
3051 AcceptedSubmission（s）:
1297
ProblemDescription
最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。
久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。
现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。
当忍耐度降到0或者0以下时，xhd就不会玩这游戏。
xhd还说了他最多只杀s只怪。
请问他能升掉这最后一级吗？
Input
输入数据有多组，对于每组数据第一行输入n，m，k，s（0分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。
接下来输入k行数据。
每行数据输入两个正整数a，b（0（每种怪都有无数个）
Output
输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。
SampleInput
101011011101019119102101122
SampleOutput
0-11
Author
Xhd
二维费用的背包问题是指：
对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代
价都有一个可付出的最大值（背包容量）。
问怎样选择物品可以得到最大的价值。
设这两种代价分别为代价1和代价2
，第i件物品所需的两种代价分别为a[i]和b[i]。
两种代价可付出的最大值（两种背包容量）分别为V和U。
物品的价值
为w[i]。
费用加了一维，只需状态也加一维即可。
设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。
状态转移方程就是：
f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}
如前述方法，可以只使用二维的数组：
当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题
时采用顺序的循环。
当物品有如多重背包问题时拆分物品。
for（i=1;i<=M;i++）
{
for（j=1;j<=S;j++）
for（k=1;k<=K;k++）if（i-b[k]>=0）
{
if（d[i-b[k]][j-1]+a[k]>=d[i][j]）
d[i][j]=d[i-b[k]][j-1]+a[k];
}
if（d[i][S]>=N）break;
}
一开始一点思路都木有 哎还是参考了人家的代码
啥时候能自己搞定啊
3个循环层的排放顺序无关紧要怎么放谁在内谁在外都可以
另外记住是求所有满足升级情况下的剩余最大值
一开始我求的只是满足的值没求最大值WA了接近10次啊
那叫一个难受啊
#include
#include
intn,m,k,s;
intjingyan[105],rennai[105],bag[105][105];
int_bag（）
{
inti,j,t,jieguo=-1;
memset（bag,0,sizeof（bag））;
for（i=0;i for（t=1;t<=s;t++）
for（j=rennai[i];j<=m;j++）
{
if（bag[j][t] bag[j][t]=bag[j-rennai[i]][t-1]+jingyan[i];
if（bag[j][t]>=n）jieguo=m-j>jieguo?
m-j:
jieguo;
}
returnjieguo;
}
intmain（）
{
inti,j;
while（scanf（"%d%d%d%d",&n,&m,&k,&s）!
=EOF）
{
for（i=0;i scanf（"%d%d",&jingyan[i],&rennai[i]）;
printf（"%d\n",_bag（））;
}
}
Piggy-Bank求最小值的背包hdu1114
TimeLimit:
2000/1000MS（Java/Others） MemoryLimit:
65536/32768K（Java/Others）
TotalSubmission（s）:
4603 AcceptedSubmission（s）:
2269
ProblemDescription
BeforeACMcandoanything,abudgetmustbepreparedandthenecessaryfinancialsupportobtained.ThemainincomeforthisactioncomesfromIrreversiblyBoundMoney（IBM）.Theideabehindissimple.WheneversomeACMmemberhasanysmallmoney,hetakesallthecoinsandthrowsthemintoapiggy-bank.Youknowthatthisprocessisirreversible,thecoinscannotberemovedwithoutbreakingthepig.Afterasufficientlylongtime,thereshouldbeenoughcashinthepiggy-banktopayeverythingthatneedstobepaid.
Butthereisabigproblemwithpiggy-banks.Itisnotpossibletodeterminehowmuchmoney
升级会员 