POJ 3624 Charm Bracelet【01背包】

末蓝、 2022-06-01 10:14 99阅读 0赞

## Charm Bracelet ##

#### 题目链接：[https://vjudge.net/contest/209202\#problem/L][https_vjudge.net_contest_209202_problem_L] ####

> 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 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 ≤ 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.

#### Input ####

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

## 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

#### 题意概括： ####

要组成一个手链，有n颗珠子，每颗珠子都有一定重量和价值，Bessie最多能承受m的重量，求出手链的最短价值。

#### 解题分析： ####

其实就是一个简单的01背包问题，套用模板就能写出来。

#### AC代码： ####

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    
    #define N 3410
    #define inf 99999999
    
    int main()
    {
        int i, j, n, m;
        int w[N], c[N], f[12890];
        while(~scanf("%d%d", &n, &m)){
            memset(f, 0, sizeof(f));
            for(i = 1; i <= n; i++) scanf("%d%d", &w[i], &c[i]);
            for(i = 1; i <= n; i++){
                for(j = m; j >= w[i]; j--)
                    f[j] = max(f[j], f[j-w[i]]+c[i]);
            }
            printf("%d\n", f[m]);
        }
        return  0;
    }

[https_vjudge.net_contest_209202_problem_L]: https://vjudge.net/contest/209202#problem/L