题目链接：Charm Bracelet POJ 3624

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
using namespace std;
int w[200005];
int d[200005];
int f[200005];
int main ()
{
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;i++)
    {
        cin >> w[i] >> d[i];
        for (int j=m;j>=w[i];j--)
        {
            f[j]=max(f[j],f[j-w[i]]+d[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}

问题描述

Bessie has gone to the mall’s jewelry store and spies(名词：间谍，密探；动词：突然看见，发现) a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1<=N<=3402) available charms. Each charm in the supplied list has a weight Wi(1<=Wi<=400),a desirability(愿望，有利条件，值得向往的事物，合意) factor Di(1<=Di<=100),and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1<=M<=12880).
Given that weight limit as a constraint(限制) and a list of the charms with their weights and desirability rating(等级，级别),deduce the maximum possible sum of ratings.（推导出最大可能的额定值和）

有N种物品和一个容积为M的背包。第i种物品的体积是wi，价值是di。求解将哪些物品装入背包可使价值总和最大。每种物品只有一件，可以选择或者不放（N<=3500,M<=13000）。

输入数据(Input)

Line 1: Two space-separated integers: N and M
Line 2…N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di.
第一行是整数N和M。第二行到第N+1行：每行两个整数W和D，描述一个物品的体积和价值。

输出要求(Output)

Line 1:A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints权重约束
输出一个整数，表示能放入背包的物品的最大价值总和。

输入样例(Sample Input)

4 6
1 4
2 6
3 12
2 7

输出样例(Sample Output)

23

7.5.2 解题思路
如果用最简单的办法枚举，每种物品有取和不取两种可能，则总的取法有2^N种，时间复杂度过高。

将物品编号，并用W[i]表示物品的体积，D[i]表示其价值。可以先考虑处理第N种物品，看看处理过后，剩下的问题是否和原问题相同且规模较小，这样也许就能形成递归或者递推。将问题抽象成一个函数F(N,M)，表示在前N种物品种取若干种，在其总体积不超过M的条件下所能获得的最大价值。更具一般性地，可以研究F(i,j)，即在前i种物品中取若干种，在其总体积不超过j的条件下能取得的最大价值。

将所有取法分成两类：第一类是取第i种物品，第二类是不取第i种物品。若取得了第i种物品，由于第i种物品的体积是W[i]，则剩下要做的事情就是求从前i-1种物品种选取若干种，在其总体积不超过j-W[i]的条件下所能获得的最大价值——此问题即F(i-1,j-W[i])。若不取第i种物品，则剩下的问题就变成F(i-1,j)。于是，第一类取法所能获得的最大价值是F(i-1,j-W[i])+D[i]，而第二类取法所能获得的最大价值是F(i-1,j)。

对两者做比较，较大的那个就是F(i,j)的值。还需要注意，若第i种物品的体积大于j，则不可取之。