这是有关于01背包的算法练习题，不明白如何构建动态规划，望解答 . C/C++

因为这个副作用，一直想不明白如何构建动态规划。

问题描述
　　JiaoShou消灭了百变怪，为爱琳世界赢得了和平，但他突然发现自己没有升级，这就意味着必须去喝药补血。爱琳世界的NPC卖的药已经不能满足他的需求了，他找到了爱琳唯一的药贩子-药加钱。药加钱的药有N种，第i种药的价格为wi单位的金币,可以恢复pi的血，但是每种药只有一瓶，并且第i种药也许含有添加剂。添加剂本身对JiaoShou没有任何影响，可是会发生i和j的添加剂混合起来，使教授减少ax的血。还好药加钱并不是太黑心，如果他的药中i和j混合使用有副作用的话。i不会再和其他药的添加剂一起产生副作用，j也是。
　　也就是说，如果设添加剂有M对副作用，第i对副作用由ci1、ci2产生了ki的血量减少，把ci1,ci2列成一张表的话，那么1-N这N个数字最多在表中出现1次（也可能没有副作用）。
　　现在JiaoShou有P单位金币，并且知道这M对副作用，他想知道他最多能提升多少血量？
输入格式
　　第一行为三个整数N、M、P，如题目描述。
　　第二行为N个整数，第i个整数为第i种药的提升血量。
　　第三行为N个整数，第i个整数为第i种药的价格。
　　接下来M行，每行三个数字，第i+3行为ci1、ci2、ki表示如果同时喝下ci1和ci2，JiaoShou会减少ki的血量。
输出格式
　　一个整数，为JiaoShou恢复的最大血量
样例输入
3 1 3
3 4 5
1 1 1
1 2 2
样例输出
10
样例说明
　　虽然有副作用，但是JiaoShou的钱足以把三种药都买下来喝，于是恢复了10单位的血。

　　数据规模：30%的数据：M=0
　　100%数据：
　　1<=N<=200,M<=N div 2; P<=1000
　　每种药的价格不超过P
　　每种药恢复的血量在1000以内。
　　输出答案保证在longint范围内。
　　对于副作用对应关系，100%数据满足题目描述。

试一试

#include<iostream>
#include<math.h>
using namespace std;
int main(){
    int n,m,p;
    cin>>n>>m>>p;
    int add[205], pri[205];
    for(int i=0;i<n;i++){
        cin>>add[i];
    }
    for(int i=0;i<n;i++){
        cin>>pri[i];
    }
    bool f[205]={false};
    int dp[205][1005]={0};
    int di=1;
    int ti,tj,tk;
    int a,b;
    for(int i=0;i<m;i++){
        cin>>ti>>tj>>tk;
        f[ti-1]=true;
        f[tj-1]=true;
        for(int j=1;j<=p;j++){
            if(j>=pri[ti-1] && dp[di-1][j-pri[ti-1]] + add[ti-1] > dp[di-1][j]){
                dp[di][j]=dp[di-1][j-pri[ti-1]] + add[ti-1];
                if(j+pri[tj-1]<=p)
                dp[di+1][j+pri[tj-1]]=dp[di][j] + add[tj-1] - tk;
            }
            else{
                dp[di][j]=dp[di-1][j];
            }
            if(dp[di+1][j]==0){
                dp[di+1][j]=(j>=pri[tj-1]?max(dp[di][j-pri[tj-1]] + add[tj-1], dp[di][j]):dp[di][j]);
            }
        }
        di+=2;
    }
    for(int i=0;i<n;i++){
        if(f[i])continue;
        for(int j=1;j<=p;j++){
            if(j>=pri[i]){
                dp[di][j]=max(dp[di-1][j-pri[i]] + add[i], dp[di-1][j]);
            }
            else{
                dp[di][j]=dp[di-1][j];
            }
        }
        di++;
    }
    printf("%ld", dp[n][p]);
    return 0;
}

这个我来
下面是动态转换的要点，我可以向你保证，你从网上找动态规划入门的教程，找不到比我写的更好的
你在网上找的许多题解，有关动态规划的，几乎是看不懂的，你会惊讶于他们怎么想到的，感觉差距这么大，惊为天人。
网上总有那么一大批人，他们通过数学规律得出结果，优化后，通过解出的答案去死扣理由，然后把扣出来的理由发到网上，你找的绝大部分题解正是他们扣出来的，二次加工后的产物，他不会告诉你他是靠找规律做出来的，这样显得很low。为的就是让你佩服他，显得自己很厉害很聪明，听明白没有，都是这种货色。
大家一定要小心这种货色。

动态规划的解题核心内容是填动态规划表后对解进行优化(也就是打表找规律)，
动态规划的真正难点在于试法，教课书上的那些状态转移方程是别人在打表之后，在表中找出数学规律之后，才写出来的。也就是说，要已知规律和解，才能写出状态转移方程。(搞笑，我已经知道答案还写个毛的方程)

动态规划试法的优化（斜率优化）核心是通过邻接位置，代替枚举行为。
动态规划的套路如下：（一般流程）
尝试——记忆化搜索——优化(打表找规律)——严格表结构dp——精致dp
尝试原则：
原则1：单可变参数最好只是一个值（单可变参数维度最好为低维（0维度））
原则2：可变参数个数少（越少越好找规律）
由于找数学规律不需要理由， 因此不建议在优化的时候找理由（纯装B）
下面将使用上面的方法来做题。
假设问题中w1-w5{2,2,6,5,4}
i代表可选物品{1,2,3,4…i}
r代表背包的剩余容积
dp[i][r]:
整个dp[i][r]代表在可选物品中选出不超重物品的最大价值。
• 使用动态规划法求解0/1背包问题。动态规划函数（状态转移方程），真代码/伪代码，动态规划数组dp。

dp[i][r] = max(dp[i-1][r],dp[i-1][r-w[i]]+v[i])
通过打表可以找到下面的规律，可通过此规律完成动态转换方程：

如果硬要掰理由，那么方程含义应为：
此行此列最大价值为上一行此列最大价值与(上行-wi列最大价值+vi)之间的最大值
翻译一下：
上一行此列最大价值：没有选第i个物品的最大价值
上行-wi列最大价值+vi：没有选第i-1个物品但选了第i个物品的最大价值。
因此，此题解的核心就是对第i个物品（不选/选）所得出的最大价值进行讨论。
不选——0
选——1
因此背包问题又叫0/1背包问题。