关于初级动态规划（dp的背包问题）的理解和题目加解析~~（我要成为一个dp选手.jpg）
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
-----百度百科；
DP全称是dynamic programming，这里programming不是编程，是一个表格保存之前的结果。
DP 是一种编程思想，主要用于解决最优解类型的问题。
其思路是为了求解当前的问题的最优解，使用子问题的最优解，然后综合处理，最终得到原问题的最优解。
要注意dp的两个原理：
（1）动态规划的最优化原理：
作为整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略的性质。也可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质，也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。
（2）动态规划的无后效性原则：
所谓无后效性原则，指的是这样一种性质：某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此前的历史只能通过当前的状态去影响过程未来的演变。
即：一个问题被划分成各个阶段之后，阶段K中的状态只能由阶段K+1中的状态通过状态转移方程得来，与其它状态没有关系，特别是与未发生的状态没有关系。
简而言之dp是一种没有固定形式，只有固定思路想法的，就想A*算法一样，需要根据现实问题而变化。
这样我们来根据题目来学习下。
（1）sdnu 1033
1033.采药
Description
Input
Output
Sample Input
100 5 77 92 22 22 29 87 50 46 99 90
Sample Output
133
Source
这就是一道摸板题~正好用来梳理一下我们的思路~这里我们可以用数组ma[k]来表示在时间使用量为k时，此时我们能够取得的最大利益是多少~这样的话对于另一种方向上来看，我们如果要拿第s个物品~那么对于任意的ma[k]如果存在ma[k-we[s]]+v[s]>ma[k]的情况 ~~即在此刻，拿这个物品并使此时总使用时间为k时的利益，是比之前我们找到的最大利益要大的~~那么此时我们就更新此时的ma[k]的值就好~~。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ma[1005];
int tim[105],v[105];
int main()
{
memset(ma,0,sizeof(ma));
int m,n;
cin>>m>>n;
for(int s=1;s<=n;s++)
{
cin>>tim[s]>>v[s];
}
for(int s=1;s<=n;s++)
{
for(int ti=m;ti>=tim[s];ti--)
{
if(ma[ti]<ma[ti-tim[s]]+v[s])
{
ma[ti]=ma[ti-tim[s]]+v[s];
}
}
}
cout<<ma[m]<<endl;
return 0;
}有人问道为什么这个时候ti要从m到tim[s]进行~~反向不好吗？这个时候你想想，假设在第一个时刻你加了这件物品，然后往后推得时候，你可能会再次用到拿没拿这件物品而产生的结果~~进而这就不是每个物品只有一个了~而是在使用范围内有不限制数量个，才能从前往后推~来让后面的处理考虑的之前的拿n个而产生的情况。
（2）1043
1043.采药2
Description
Input
Output
Sample Input
100 5 77 92 33 50 34 60 50 46 99 161
Sample Output
161
这道题就是之前说的~~多件物品怎么处理。发核心代码
for(int s=1;s<=n;s++)
{
for(int ti=tim[s];ti<=m;ti++)
{
if(ma[ti]<ma[ti-tim[s]]+v[s])
{
ma[ti]=ma[ti-tim[s]]+v[s];
}
}
}（3）sdnu1061
1061.采药3
Description
Input
Output
Sample Input
100 100 5 50 60 100 60 50 120 50 50 115 40 60 21 40 50 5
Sample Output
125
这是一个有两个限制条件的dp，这样的话我们ma[a][b]来表示重量为a,体积为b时的最大利益是多少~这样的话一化简就好了~就相当于把第一个方程加了重循环。（mw，mv分别表示背包最大承受重量和容量）
for(int s=1;s<=n;s++)
{
for(int a=mw;a>=we[s];a--)
{
for(int b=mv;b>=vol[s];b--)
{
if(ma[a][b]<ma[a-we[s]][b-vol[s]]+v[s])
{
ma[a][b]=ma[a-we[s]][b-vol[s]]+v[s];
}
}
}
}（4）sdnu1077
1077.采药4
Description
Input
Output
Sample Input
100 5 55 40 59 44 2
Sample Output
1
这道题他奇怪的地方是~他要求的不是最大利益，而是最小的空间剩余度，那么我们用ma[k]来表示能否用物品凑齐容量为k的空间。这样的话状态转移方程为 if(ma[w]&& !ma[w+we[s]]) ma[w+we[s]]=1;
这样的话我们在处理完之后从最大的m到0开始看，最先ma值为1的就是答案~
for(int s=1;s<=n;s++)
{
for(int w=m-we[s];w>=0;w--)
{
if(ma[w]&&!ma[w+we[s]])
{
ma[w+we[s]]=1;
}
}
}
for(int s=m;s>=0;s--)
{
if(ma[s])
{
cout<<m-s<<endl;
return 0;
}
}（5）sdnu1520
1520.采药
Description
SQK上山去采药。SQK有一个容量为m(1<=m<=1000)的背包，他所采集的药材的总重量不能大于背包的容量。已知共有n(1<=n<=100 )种药材，每种药材都有自己的价值，并且知道每种药材的数量是有限的，如何选择，才能使得背包中药材价值最大？
Input
输入数据首先包含一个正整数C(1<=C<=10)，表示有C组测试用例，每组测试用例的第一行是两个整数m和n(1<=m<=1000, 1<=n<=100),分别表背包的负重和药材的种类，然后是n行数据，每行包含3个数w，v和c(1<=w<=100,1<=v<=200,1<=c<=100)，分别表示每种药材的重量、每株的价值以及对应种类药材的株数。
Output
对于每组测试数据，请输出能够采集药材的最大价值，每个实例的输出占一行。
Sample Input
18 22 100 44 100 2
Sample Output
400
这道题其实跟第一题一样的~有n个同一个物体~跟有n个属性一样的物体~这两个表达有什么区别~~加一个循环就行了
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ma[1005];
int we[105],vi[105],sum[105];
int main()
{
int te;
cin>>te;
while(te--)
{
memset(ma,0,sizeof(ma));
int m,n;
cin>>m>>n;
for(int s=1;s<=n;s++)
{
cin>>we[s]>>vi[s]>>sum[s];
}
for(int s=1;s<=n;s++)
{
for(int k=0;k<sum[s];k++)
{
for(int w=m;w>=we[s];w--)
{
if(ma[w]<ma[w-we[s]]+vi[s])
{
ma[w]=ma[w-we[s]]+vi[s];
}
}
}
}
cout<<ma[m]<<endl;
}
return 0;
}
字节跳动公司氛围 550人发布
