HDOJ(HDU).3466 Dividing coins ( DP 01背包 无后效性的理解)

题意分析

要先排序，在做01背包，否则不满足无后效性，为什么呢？

等我理解了再补上。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 505

#define nn 505*100

using namespace std;

struct item{

    int p;

    int q;

    int v;

    int rate;

}a[nmax];

int dp[nn];

bool cmp(item x, item y)

{

    return x.rate<y.rate;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int N,M;

    while(scanf("%d%d",&N,&M)!= EOF){

        memset(dp,0,sizeof(dp));

        for(int i = 1; i<= N;++i) {scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v); a[i].rate = a[i].q - a[i].p;}

        sort(a+1,a+1+N,cmp);

        for(int i = 1; i<=N;++i){

            for(int j =M;j>=a[i].q;--j)

                dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);

        }

        printf("%d\n",dp[M]);

    }

    return 0;

}