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

Question

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

问题描述
　　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%数据满足题目描述。

Answer 1

试一试

#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;
}