POJ 3624 Charm Bracelet（01背包，裸题）

题目意思：
有N个物品，分别有不同的重量Wi和价值Di，Bessie只能带走重量不超过M的物品，要是总价值最大，并输出总价值。
本题要点：
1、裸的 01背包题目。
参考代码 ：《算法竞赛进阶指南》 276页。
开一维数组 dp
2、状态表示：
dp[j] 表示 背包中放入总体积为j的物品的最大价值。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 3500, MaxM = 13000;
int v[MaxN], w[MaxN];
int dp[MaxM];
int n, m;void solve()
{
    memset(dp, 0xcf, sizeof dp);dp[0] = 0;for(int i = 1; i <= n; ++i){
    for(int j = m; j >= v[i]; --j){
    dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}}int ans = 0;for(int j = 0; j <= m; ++j){
    ans = max(ans, dp[j]);}printf("%d\n", ans);
}int main()
{
    scanf("%d%d", &n, &m);for(int i =1; i <= n; ++i){
    scanf("%d%d", &v[i], &w[i]);}solve();return 0;
}/* 4 6 1 4 2 6 3 12 2 7 *//* 23 */