当前位置：首页 > news >正文

2025.7.24 01背包与动态规划复习总结

news 2025/7/28 5:52:39

首先，01背包的公式：

dp[j]=max(dp[j-1],dp[j-w[i]]+v[i]);

P1048 [NOIP 2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 2 个整数 T（1≤T≤1000）和 M（1≤M≤100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。

接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例

输入 #1

输出 #1

说明/提示

【数据范围】

对于 30% 的数据，M≤10；
对于全部的数据，M≤100。

【题目来源】

NOIP 2005 普及组第三题

解法

就直接使用开头所讲的公式来写这道题就可以了，一道模板题

题解

for(int i=1;i<=m;i++)for(int j=t;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

错误

应该输出dp[t]，写成了dp[m]

P1049 [NOIP 2001 普及组] 装箱问题

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。

现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 V，表示箱子容量。

第二行共一个整数 n，表示物品总数。

接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。

输出格式

共一行一个整数，表示箱子最小剩余空间。

输入输出样例

输入 #1

输出 #1

说明/提示

对于 100% 数据，满足 0<n≤30，1≤V≤20000。

【题目来源】

NOIP 2001 普及组第四题

解法

跟上一道题差不多，求出dp[t]后再用t减dp[t]就可以了，没有什么要改的

题解

for(int i=1;i<=n;i++)for(int j=t;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
cout<<t-dp[t];

P2925 [USACO08DEC] Hay For Sale S

题目描述

农民 John 面临一个很可怕的事，因为防范力度不大所以他存储的所有稻草都被蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，John 拉着他的马车到农民 Don 的农场中买一些稻草给奶牛过冬。已知 John 的马车可以装的下 C(1≤C≤5×10的4次方) 立方的稻草。

农民 Don 有 H(1≤H≤5×10的3次方) 捆体积不同的稻草可供购买，每一捆稻草有它自己的体积 Vi(1≤Vi≤C)。面对这些稻草 John 认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。

现在给定马车的最大容积 C 和每一捆稻草的体积 Vi，John 如何在不超过马车最大容积的情况下买到最大体积的稻草？他不可以把一捆稻草分开来买。

输入格式

第一行两个整数，分别为 C 和 H。第 2 到 H+1 行:每一行一个整数代表第 i 捆稻草的体积 Vi。

输出格式

一个整数，为 John 能买到的稻草的体积。

修改 by zhangsenhao6728

题意翻译

显示翻译

输入输出样例

输入 #1

输出 #1

解法

这里的w[i]和v[i]其实可以看做同一个数，然后再用同样的方法求就可以了

题解

for(int i=1;i<=n;i++)
{cin>>w[i];v[i]=w[i];
}
for(int i=1;i<=n;i++)for(int j=t;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

P1510 精卫填海

题目描述

本题为改编题。

发鸠之山，其上多柘木。有鸟焉，其状如乌，文首，白喙，赤足，名曰精卫，其名自詨。是炎帝之少女，名曰女娃。女娃游于东海，溺而不返，故为精卫。常衔西山之木石，以堙于东海。——《山海经》

精卫终于快把东海填平了！只剩下了最后的一小片区域了。同时，西山上的木石也已经不多了。精卫能把东海填平吗？

事实上，东海未填平的区域还需要至少体积为 v 的木石才可以填平，而西山上的木石还剩下 n 块，每块的体积和把它衔到东海需要的体力分别为 k 和 m。精卫已经填海填了这么长时间了，她也很累了，她还剩下的体力为 c。

输入格式

输入文件的第一行是三个整数：v,n,c。

从第二行到第 n+1 行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式

输出文件只有一行，如果精卫能把东海填平，则输出她把东海填平后剩下的最大的体力，否则输出 Impossible（不带引号）。

输入输出样例

输入 #1

100 2 10
50 5
50 5

输出 #1

输入 #2

10 2 1
50 5
10 2

输出 #2

Impossible

说明/提示

数据范围及约定

对于 20% 的数据，0<n≤50；
对于 50% 的数据，0<n≤1000；
对于 100% 的数据，0<n≤10的4次方，所有读入的数均属于 [0,10的4次方]，最后答案不大于 c。

解法

这边要先输入v[i]再输入w[i],然后如果不能输出Impossible的话就要while循环来找最小的那个

题解

for(int i=1;i<=n;i++)for(int j=c;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
if(dp[c]<t) cout<<"Impossible";
else
{int j=c;while(dp[j]>=t) j--;cout<<c-j-1;
}

错误

这里要输出c-j-1，原本写的是c-dp[j]

P1926 小书童——刷题大军

题目背景

数学是火，点亮物理的灯；物理是灯，照亮化学的路；化学是路，通向生物的坑；生物是坑，埋葬学理的人。
文言是火，点亮历史宫灯；历史是灯，照亮社会之路；社会是路，通向哲学大坑；哲学是坑，埋葬文科生。——小 A

题目描述

小 A “刷题”十分猖狂，明目张胆地“刷题”。他现在在小书童里发现了 n 样他喜欢的“题目”，每“题”都有他的需要时间，而老师布置了 m 项作业，每项作业都有它的需要时间及分值，老师规定 k 分以上算及格。小 A 只剩 r 个单位时间，他想在及格的基础上更多地“刷题”。

输入格式

第一行四个整数 n,m,k,r。

第二行有 n 个数，代表每“题”他的需要时间。

第三行有 m 个数，表示每项作业它的需要时间。

第四行有 m 个数，代表每项作业它的分值。

输出格式

一个数，代表小 A 能刷几道题。

输入输出样例

输入 #1

3 4 20 100
15 20 50
10 15 40 40
5 5 10 15

输出 #1

说明/提示

数据范围及约定

对于 100% 的数据，n≤10，m≤10，k≤50，r≤150。数据保证没有不能及格的情况。

解法

题目背景里的生物和化学是秦始皇吗（？）

好了，这道题相当于两个问题，先求你最小需要的时间（保证及格），然后再通过排序来求小A最多可以刷的题，跟前面的题也差不多

题解

for(int i=1;i<=m;i++)for(int j=r;j>=w[i];j--)dp[j]=max(dp[j-1],dp[j-w[i]]+v[i]);
for(int i=1;i<=r;i++)if(dp[i]>=k){r-=i;break;}	
sort(a+1,a+n+1);
int sum=0,cnt=0;
for(int i=1;i<=n;i++)
{if(sum+a[i]<=r){sum+=a[i];cnt++;}else break;
}

P1802 5 倍经验日

题目背景

现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。

题目描述

现在 absi2011 拿出了 x 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。

由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 2 个药去打别人，别人却表明 3 个药才能打过，那么相当于你输了并且这两个属性药浪费了。

现在有 n 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。

要求求出最大经验 s，输出 5s。

输入格式

第一行两个数，n 和 x。

后面 n 行每行三个数，分别表示失败时获得的经验 losei，胜利时获得的经验 wini 和打过要至少使用的药数量 usei。

输出格式

一个整数，最多获得的经验的五倍。

输入输出样例

输入 #1

输出 #1

说明/提示

【Hint】

五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。

【数据范围】

对于 10% 的数据，保证 x=0。
对于 30% 的数据，保证 0≤n≤10，0≤x≤20。
对于 60% 的数据，保证 0≤n,x≤100， 10<losei,wini≤100，0≤usei≤5。
对于 100% 的数据，保证 0≤n,x≤10的3次方，0<losei≤wini≤10的6次方，0≤usei≤10的3次方。

【题目来源】

fight.pet.qq.com

absi2011 授权题目

解法

只需要再原有公式的基础上改变，因为如果你就算没打过也有lose[i]点经验，所有dp[j-1]应该加上lose[i]，注意最后输出要×5

题解

for(int i=1;i<=n;i++)for(int j=x;j>=0;j--){dp[i][j]=dp[i-1][j]+l[i];if(j-a[i]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+w[i]);}

P1877 [HAOI2012] 音量调节

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。输入文件中整数 beginLevel，代表吉他刚开始的音量，整数 maxLevel，代表吉他的最大音量。音量不能小于 0 也不能大于 maxLevel。输入中还给定了 n 个整数 c1,c2,c3,⋯,cn，表示在第 i 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

输入格式

第一行依次为三个整数 n，beginLevel 和 maxLevel。

第二行依次为 n 个整数 c1,c2,c3,⋯,cn。

输出格式

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 0 或者高于 maxLevel，输出 -1。

输入输出样例

输入 #1

3 5 10
5 3 7

输出 #1

说明/提示

1≤n≤50，1≤ci≤beginLevel，1≤maxLevel≤1000，0≤beginLevel≤maxLevel。

解法

这道题就跟背包没关系了，我们把dp看成一个标记数组就可以了，把每个符合范围的数标记为1，然后求dp[n][i]中的最大值就可以了

题解

dp[0][b]=1;
for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){if(dp[i-1][j-c[i]]==1&&j-c[i]>=0) dp[i][j]=1;if(dp[i-1][j+c[i]]==1&&j+c[i]<=m) dp[i][j]=1;}
for(int j=0;j<=m;j++)if(dp[n][j]==1) mx=max(mx,j);