Charm Bracelet poj3624（01背包）

http://poj.org/problem?id=3624

题意：现给你一个包的承重量为M，然后有各种手链的重量Wi,以及它们的价值Di,问你能得到的最大价值为多少？

分析：典型的01背包问题

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#include <iostream>
#include<algorithm>
#include<queue>
#define maxn 15000
using namespace std;
int dp[maxn], w[maxn], d[maxn];

int main()
{
    int n, m;

    while(scanf("%d %d", &n, &m)!=EOF)
    {
        for(int i=1; i<=n; i++)

            scanf("%d %d", &w[i], &d[i]);

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

        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
", dp[m]);
    }
    return 0;
}