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

Dear 丶 2021-12-03 14:51 186阅读 0赞

[**题目链接**][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;52318</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;21912</td> 
  </tr> 
 </tbody> 
</table>

**Description**

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

**AC代码（模板题）**

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 13000;
    int dp[N];
    int s, n;//背包容积和物品数量
    
    struct Thing
    {
        int w;
        int v;
    }list[3405];
    
    void init()
    {
        for (int i = 0; i <= s; i++)dp[i] = 0;
    }
    
    void package()
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = s; j >= list[i].w; j--)
            {
                dp[j] = max(dp[j], dp[j - list[i].w] + list[i].v);
            }
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &s);
        for (int i = 0; i < n; i++)scanf("%d%d", &list[i].w, &list[i].v);
        init();
        package();
        printf("%d", dp[s]);
        return 0;
    }

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    using namespace std;
    
    int n, m;
    int dp[13000];
    
    struct Thing
    {
        int w, v;
    }list[3500];
    
    int package()
    {
        for (int i = 0; i <= m; i++)dp[i] = 0;
        for (int i = 0; i < n; i++)//循环n次，放入n个物品
        {
            for (int j = m; j >= list[i].w; j--)
            {
                dp[j] = max(dp[j], dp[j - list[i].w] + list[i].v);
            }
        }
        return dp[m];
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)scanf("%d%d", &list[i].w, &list[i].v);
        printf("%d\n", package());
        return 0;
    }

二刷

转载于:https://www.cnblogs.com/yun-an/p/11105955.html

[Link 1]: http://poj.org/problem?id=3624
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211203/bc8d1afefa3749bb9cb00eecffd085b3.png