http://acm.hdu.edu.cn/showproblem.php?pid=5410

完全背包的依赖，属于树形DP

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
#define N 1005
#define INF 25000005
int weight[N],price[N],r[N];
int dp[N*2];
int main(){
    int T;scanf("%d",&T);
    while(T--){
        memset(dp,sizeof(dp));
        int M,n;scanf("%d%d",&M,&n);
        int i,j;
        for(i=0;i<n;i++) scanf("%d%d%d",&price[i],&weight[i],&r[i]);

        for(i=0;i<n;i++){
            for(j=M;j>=price[i];j--)
                dp[j]=max(dp[j],dp[j-price[i]]+weight[i]+r[i]);
            for(j=price[i];j<=M;j++)
                dp[j]=max(dp[j],dp[j-price[i]]+weight[i]);
        }
        printf("%d\n",dp[M]);

    }//while
    return 0;
}//main