poj 3624 - Charm Bracelet

╰半夏微凉° 2022-06-08 07:21 100阅读 0赞

# 1. 地址 #

[http://poj.org/problem?id=3624][http_poj.org_problem_id_3624]

# 2. 定位 #

*  动态规划
 *  0-1背包

# 3. 分析 #

典型0-1背包，具体思路见 [hdu 2602][]。

# 4. 代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    int weight[3403];
    int value[3403];
    int dp[12881];
    
    int main()
    {
        int N,M;
        int i,j;
    
        scanf("%d*c",&N);
        scanf("%d*c",&M);
        memset(weight,0,sizeof(weight));
        memset(value,0,sizeof(value));
        memset(dp,0,sizeof(dp));
        for(i=1; i<=N; i++)
        {
            scanf("%d %d*c",&weight[i],&value[i]);
        }
        for(i=1; i<=N; i++)
        {
            for(j=M; j>=weight[i]; j--)
            {
                dp[j] = dp[j-weight[i]] + value[i] > dp[j] ? dp[j-weight[i]] + value[i] : dp[j];
            }
        }
        printf("%d\n",dp[M]);
        return 0;
    }

# 5. 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">282MS</td> 
   <td align="center">504K</td> 
   <td align="center">586B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

Ver 1.0 2017-9-18

[http_poj.org_problem_id_3624]: http://poj.org/problem?id=3624
[hdu 2602]: http://blog.csdn.net/moonspiritacm/article/details/55051635

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 136 阅读

相关 poj-3624Charm Bracelet

Charm Bracelet <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000

谁践踏了优雅/ 2022年08月09日 13:39/ 0 赞/ 2 阅读

相关 Charm Bracelet

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

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

相关 01背包问题 poj 3624

理解01背包问题，首先要从二维数组的开始。二维数组的理解之后，优化成为一维，就是轻而易举的事了。 01背包动态规划的转移公式：当考虑第i件物品的时候，背包能装得下的话

落日映苍穹つ/ 2022年06月13日 10:50/ 0 赞/ 119 阅读

相关 poj 3624 - Charm Bracelet

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

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

相关 POJ 3624 Charm Bracelet【01背包】

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

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

相关 poj3624 Charm Bracelet

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

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

相关 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 赞/ 219 阅读

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

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

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

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

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

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