POJ.3624 Charm Bracelet(DP 01背包)

题意分析

裸01背包

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define nmax 13000

#define nnmax 3500

using namespace std;

int dp[nmax];

int w[nnmax],d[nnmax];

int main()

{

    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",&w[i],&d[i]);

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

            for(int j = m; j>=w[i];--j)

                dp[j] = max(dp[j],dp[j-w[i]]+d[i]);

        }

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

    }

    return 0;

}