【每日一题24】AcWing 426. 开心的金明

发表于 更新于 分类于 Valine：
本文字数： 122 阅读时长 ≈ 1 分钟

Day24 AcWing 426. 开心的金明

思路

  1. 01背包
  2. 转换后
    • 总钱数相当于背包总容量
    • 每件物品的价格相当于体积
    • 每件物品的价格乘以重要度相当于价值
  3. 01背包问题的时间复杂度是 $O(nm)$，其中 $n$ 是物品个数，$m$ 是背包容量。

类似题目

  1. 01背包问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30, M = 30010;

int n, m;
int f[M];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int v, w;
        cin >> v >> w;
        w = v * w;
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[m] << endl;
    return 0;
}