DP动态规划练习——01背包
❤作者：那些年丶我们逃过的课
❤博客主页：那些年丶我们逃过的课的博客_CSDN博客-c++题目,c++学习记录,c++小游戏领域博主
❤码云gitee：我的码云 - Gitee.com
❤期待你的关注，如果觉得还可以的话，可以点赞评论支持一下，每个评论我都会回访的🎉
对01背包问题还不太了解的可以看：DP动态规划入门学习记录（三）——01背包_那些年丶我们逃过的课的博客-CSDN博客
P1049 [NOIP2001 普及组] 装箱问题
有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（0<n≤30)，每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出格式
11个整数，表示箱子剩余空间。
输入输出样例
输入 #1
2468312797输出 #1
0说明/提示
【题目来源】
NOIP 2001 普及组第四题
DP代码
#includeusing namespace std;int f[100000];int v,n;int s[1000];int main(){cin>>v>>n;for(int i=1;i>s[i];f[0]=0;for(int i=1;i=s[i];j--){f[j]=max(f[j-s[i]]+s[i],f[j]);}}cout<<v-f[v];return 0;}P1616 疯狂的采药
题目描述
LiYuxiang 是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是 LiYuxiang，你能完成这个任务吗？
此题和原题的不同点：
-
每种草药可以无限制地疯狂采摘。
-
药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！
输入格式
输入第一行有两个整数，分别代表总共能够用来采药的时间 t和代表山洞里的草药的数目 m。
第 22 到第 (m + 1) 行，每行两个整数，第 (i + 1)行的整数 a i , b i a_i, b_i ai,bi分别表示采摘第 i 种草药的时间和该草药的价值。
输出格式
输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
输入输出样例
输入 #1
70 371 10069 11 2输出 #1
140说明/提示
数据规模与约定
- 对于 30% 的数据，保证 m ≤ 103 m≤10^3 m≤103。
- 对于 100% 的数据，保证 1 ≤ m ≤ 104 , 1 ≤ t ≤ 107 1≤m≤10^4,1≤t≤10^7 1≤m≤104,1≤t≤107，且 1 ≤ m × t ≤ 107 , 1 ≤ a i , b i ≤ 104 1≤m×t≤10^7,1≤a~i,b~i≤10^4 1≤m×t≤107,1≤a i,b i≤104。
DP代码
#includeusing namespace std;int main(){long long a,b;long long w[100005],v[100005];long long f[10000005]={0};cin>>a>>b;for(long long i=1;i>w[i]>>v[i];for(long long i=1;i<=b;i++){for(long long j=w[i];j<=a;j++){f[j]=max(f[j],f[j-w[i]]+v[i]); }}cout<<f[a];return 0;}P1060 [NOIP2006 普及组] 开心的金明
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为55等：用整数1-5表示，第55等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j 1 , j 2 , … , j k j_1,j_2,…,j_k j1,j2,…,jk，则所求的总和为：
v [ j 1 ] × w [ j 1 ] + v [ j 2 ] × w [ j 2 ] + … + v [ j k ] × w [ j k ] v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k]\times w[j_k] v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]。
请你帮助金明设计一个满足要求的购物单。
输入格式
第一行，为2个正整数，用一个空格隔开：n,m（其中N(<30000)表示总钱数，m(<25)为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j−1的物品的基本数据，每行有2个非负整数v p（其中v表示该物品的价格( v ≤ 10000 v \le 10000 v≤10000)(v≤10000)，p表示该物品的重要度(1−5)
输出格式
1个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(<100000000)。
输入输出样例
输入 #1
1000 5800 2400 5300 5400 3200 2输出 #1
3900说明/提示
NOIP 2006 普及组 第二题
DP代码
#includeusing namespace std;long long v[100000];long long q[100000];long long f[100000];int main(){int n,m;cin>>n>>m;for(int i=1;i>q[i]>>b;v[i]=q[i]*b;}f[0]=0;for(int i=1;i=q[i];j--){f[j]=max(f[j],f[j-q[i]]+v[i]);}}cout<<f[n];return 0;}对01背包问题还不太了解的可以看：DP动态规划入门学习记录（三）——01背包_那些年丶我们逃过的课的博客-CSDN博客