题目描述

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 available charms. Each charm i in the supplied list has a weight , a 'desirability' factor , and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than .
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.

输入描述:

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: and

输出描述:

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

示例1

输入
4 6
1 4
2 6
3 12
2 7
输出
23

解答

关于01背包的定义：
所谓01背包，即只有两种情况，一种是0，一种是1。
即对于一个物品，我们有两种选择，一种是拿走它，另一种是不拿它
那么我们来看看这道题
有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
感谢不知名大神的翻译，这让我们看一眼就知道这题是01背包的模板题
这是最基础的01背包,是最白的，是最纯洁的，是不加任何修饰的
根据01背包的定义，我们很容易可以得到状态转移方程

那么就可以开始一波玄学操作了 
#include<iostream>
#include<cstdio>

using namespace std;

int n,m;
int c[3500],w[3500];
int f[12880];
//f[i]代表 当体积为i是能获得的价值 最大值 

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&w[i]);
        //c是该物品的体积 ，w是该物品的价值 
    }

    for(int i=1;i<=n;i++)
    //枚举每一个物品 
    {
        for(int j=m;j>=0;j--)
        //倒着枚举体积
        //记住要倒着 
        {
            //如果目前背包的体积可以装得下当前这个物品 
            if(j>=c[i])
            {
                //那就看看要不要拿这个物品
                //即是拿它获得的价值大，还是不拿它,拿其他的物品得到的价值大 
                f[j]=max(f[j],f[j-c[i]]+w[i]);
                //这里就是01背包的核心部分
                //j-c[i]即 拿走当前这个物品后背包剩余的体积
                //+w[i]即 拿走该物品能得到的最大值
                //这一步也是为什么要倒着枚举体积的原因 
            }
        }
    }

    printf("%d",f[m]);

    return 0;
}

特别基础的01背包哦！
记得倒着枚举体积哦！

来源：Mi_manchi 的博客