P 老师需要去商店买 nnn 支铅笔作为小朋友们参加 NOIP 的礼物。她发现商店一共有 333 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P 老师决定只买同一种包装的铅笔。 商店不允许将铅笔的包装拆开，因此 P 老师可能需要购买超过 nnn 支铅笔才够给小朋友们发礼物。 现在 P 老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 nnn 支铅笔最少需要花费多少钱。 输入格式 第一行包含一个正整数 nnn，表示需要的铅笔数量。 接下来三行，每行用 222 个正整数描述一种包装的铅笔：其中第 111 个整数表示这种包装内铅笔的数量，第 222 个整数表示这种包装的价格。 保证所有的 777 个数都是不超过 100001000010000 的正整数。 输出格式 111 个整数，表示 P 老师最少需要花费的钱。

这是一个简单的背包问题，可以使用动态规划求解。具体来说，设 f(i,j) 表示前 i 种包装，购买 j 支铅笔所需的最小花费，那么有以下状态转移方程：

f(i,j) = min{f(i-1,j-k*num[i])+k*price[i] | 0<=k*num[i]<=j}

其中 num[i] 表示第 i 种包装内铅笔的数量，price[i] 表示第 i 种包装的价格。上述方程的意思是，考虑购买第 i 种包装内的铅笔，可以购买 0 到 j/num[i] 个，分别计算出对应的花费，取最小值即可。

最终答案为 f(333,n)，即购买所有包装内铅笔数量都足够的情况下，购买 n 支铅笔所需的最小花费。

以下是 Python 代码实现：

n = int(input())
num = [0] * 334
price = [0] * 334
for i in range(1, 334):
num[i], price[i] = map(int, input().split())

INF = 0x3f3f3f3f
f = [[INF] * (n+1) for _ in range(334)]
f[0][0] = 0
for i in range(1, 334):
for j in range(n+1):
for k in range(j//num[i]+1):
f[i][j] = min(f[i][j], f[i-1][j-k*num[i]]+k*price[i])

print(f[333][n])

相关问题

c++描述 P老师需要去商店买 n 支铅笔作为小朋友们参加NOIP的礼物。她发现商店一共有三种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起见，P老师决定只买同一种包装的铅笔。 商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过 n 支铅笔才够给小朋友们发礼物。 现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 n 支铅笔最少需要花费多少钱。 输入描述 第一行包含一个正整数 n ，表示需要的铅笔数量。 接下来三行，每行用 2 个正整数描述一种包装的铅笔，其中： 第 1个整数表示这种包装内铅笔的数量 第 2个整数表示这种包装的价格。 保证所有的 2个数都是不超过 10000的正整数。 输出描述 1个整数，表示P老师最少需要花费的钱。

好的，下面是 C++ 代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;

int n;
int f[MAXN];

struct Pencil {
    int num, price;
} p[3];

int main() {
    cin >> n;
    memset(f, INF, sizeof(f));
    f[0] = 0;
    for (int i = 0; i < 3; ++i) {
        cin >> p[i].num >> p[i].price;
        for (int j = p[i].num; j <= n; ++j) {
            f[j] = min(f[j], f[j - p[i].num] + p[i].price);
        }
    }
    cout << f[n] << endl;
    return 0;
}

读入铅笔包装的数量和价格，从小到大枚举铅笔数量，使用状态转移方程更新 $f_i$ 的值。最后输出 $f_n$ 即可。

注意，由于初始化 $f$ 为 $+\infty$，因此不能直接加上 $p[i].price$ 来更新 $f_{j}$，否则会出现整型溢出的问题。

p1909 [noip2016 普及组] 买铅笔

题目描述

小明想买 $n$ 支铅笔，商店出售 $m$ 种铅笔，每种铅笔的数量无限，第 $i$ 种铅笔的价格为 $a_i$ 元。请问小明最少需要花多少元才能买到 $n$ 支铅笔。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $m$ 个整数，表示每种铅笔的价格 $a_i$。

输出格式

输出一个整数，表示小明最少需要花多少元才能买到 $n$ 支铅笔。

数据范围

$1≤n,m≤100$,

$1≤a_i≤100$

输入样例

5 2
4 2

输出样例

8

算法1

(贪心) $O(n)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码