题解 P2871 【[USACO07DEC]手链Charm Bracelet】

· · 题解

本蒟蒻终于理解了零一背包。( •̀ ω •́ ) 耶

第一次题解。

先配一下我的翻译。

贝茜在逛珠宝店时，买了一个她喜欢的手镯。因此她想从她收集的N（1≤N≤3402）块宝石中选最好的一些镶在手镯上。对于第i块宝石，它的重量为Wi（1≤Wi≤400），并且可以给贝茜增加魅力值Di（1≤Di≤100）。由于贝茜只能忍受重量不超过M（1≤M≤12880）的手镯，她可能无法把所有她喜欢的宝石都镶上。

于是贝茜找到了你，希望你能帮她计算，按照最合理的方案镶宝石，她的魅力值最多能增加多少。

由于每块宝石各不相同，所以典型的零一背包啦。

如果f数组是二维的，肯定是要爆空间的。 （只是本蒟蒻认为其实一维的比较好理解）

话不多说，代码见下。

#include<bits/stdc++.h>
using namespace std;
int w[3410],v[3410];  //w数组存重量，v数组存价值（魅力值）
int f[13000];
int main()
{
    int n,m;   //m是最大重量
    cin>>n>>m;     //与采药输入顺序相反
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];  //输入好像没什么好说的。
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=w[i];j--)   //从后向前找不会有其它影响
        {
            f[j]=max(f[j-w[i]]+v[i],f[j]);   //最基本的状态转移方程
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

蒟蒻的第一次题解。管理大大求过