题解 | Charm Bracelet-牛客假日团队赛6H题

H-Charm Bracelet_牛客假日团队赛6

https://ac.nowcoder.com/acm/contest/993/H

题目描述

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 ≤ 3,402)$ available charms. Each charm i in the supplied list has a weight $W_i (1 ≤ W_i ≤ 400)$ , a 'desirability' factor $D_i (1 ≤ D_i ≤ 100)$ , and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than $M (1 ≤ M ≤ 12,880)$ .
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: $W_i$ and $D_i$

输出描述:

* 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背包的定义，我们很容易可以得到状态转移方程

$f[i]=f[i-wight[j]]+money[j];$

那么就可以开始一波玄学操作了

#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 的博客