Charm Bracelet（经典例题0-1背包）

Love The Way You Lie 2022-11-19 04:27 113阅读 0赞

https://ac.nowcoder.com/acm/problem/25029  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]

输出23

**solution1**  
这个方法会爆

#include <bits/stdc++.h>
    const int maxn = 3405;
    
    using namespace std;
    int w[maxn],c[maxn];
    int dp[12888][12888];
    
    int main ()
    { 
        int n, m;
        cin >> n >> m;
        for (int i =  1; i <= n; i++){ 
            cin >> w[i] >> c[i];
        }
        for (int i = 1; i <= n; i++){ 
            for(int j = 1; j <= m; j++){ 
                if(j < w[i])
                    dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i]);
            }
        }
        cout << dp[n][m]<<endl;
        return 0;
    }

**solution2**

#include <bits/stdc++.h>
    const int maxn = 3405;
    
    using namespace std;
    int w[maxn],c[maxn],dp[12888];
    
    int main ()
    { 
        int n, m;
        cin >> n >> m;
        for (int i =  1; i <= n; i++){ 
            cin >> w[i] >> c[i];
        }
        for (int i = 1; i <= n; i++){ 
            for(int j = m; j >= 1; j--){ 
                if(j >= w[i]) 
                    dp[j] = max(dp[j], dp[j-w[i]]+c[i]);
            }
        }
        cout << dp[m]<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1a2VyNg_size_16_color_FFFFFF_t_70]: /images/20221022/987c7a9a0e7145689856852d8ea4abf6.png

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关 Charm Bracelet（经典例题0-1背包）

https://ac.nowcoder.com/acm/problem/25029 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVp

Love The Way You Lie/ 2022年11月19日 04:27/ 0 赞/ 114 阅读

相关【置顶】经典背包讲解01背包&&完全背包&&多重背包

收藏几个好的有关背包的博文： 1.背包入门：[点击打开链接][Link 1] 2.背包九讲：[点击打开链接][Link 2] [ ][Link 3]

旧城等待，/ 2022年07月19日 05:12/ 0 赞/ 197 阅读

相关 Charm Bracelet

题目：描述 Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of cour

淩亂°似流年/ 2022年07月14日 13:58/ 0 赞/ 13 阅读

相关 10背包例题

一个院级的acm小选拔赛，遇到的几个简单题目，这里做下总结越野跑问题 include <iostream> using namespace std;

末蓝、/ 2022年07月14日 03:11/ 0 赞/ 110 阅读

相关 poj 3624 - Charm Bracelet

1. 地址 [http://poj.org/problem?id=3624][http_poj.org_problem_id_3624] 2. 定位动态规

╰半夏微凉°/ 2022年06月08日 07:21/ 0 赞/ 72 阅读

相关 POJ 3624 Charm Bracelet【01背包】

Charm Bracelet 题目链接：[https://vjudge.net/contest/209202\problem/L][https_vjudge.net_c

末蓝、/ 2022年06月01日 10:14/ 0 赞/ 75 阅读

相关 poj3624 Charm Bracelet

Charm Bracelet Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 44500 Acc

爱被打了一巴掌/ 2022年05月26日 23:08/ 0 赞/ 79 阅读

相关 Charm Bracelet POJ - 3624 (利用滚动数组解决01背包)

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd

雨点打透心脏的1/2处/ 2022年02月24日 14:54/ 0 赞/ 193 阅读

相关 POJ 3624 Charm Bracelet(01背包模板题)

[题目链接][Link 1] <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

Dear 丶/ 2021年12月03日 14:51/ 0 赞/ 186 阅读

相关 POJ—— 3624 Charm Bracelet（01背包）

题目链接：[http://poj.org/problem?id=3624][http_poj.org_problem_id_3624] 题目： Charm

红太狼/ 2021年09月26日 11:36/ 0 赞/ 174 阅读