← 返回题目
题库练习 多重背包
← 上一题 下一题 →

A690 | 多重背包

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定容量为 $m$的背包，以及$n$ 种物品。
每种物品有 $3$ 个属性，$w_i, v_i, cnt_i$ 分别表示第 $i$ 种物品的体积、价值、数量 。
请求出不超过背包容量的情况下可获得的最大价值。

输入格式

第一行输入两个整数 $m$ 和 $n$，分别表示背包的大小和物品的数量。
接来下 $n$ 行，每行三个整数 $w_i, v_i, cnt_i$，分别表示第 $i$ 种物品的体积、价值、数量。

输出格式

一个整数表示最大价值

输入输出样例

输入 #1
10 1
5 100 1
输出 #1
100
C++ 编辑器
输入
输出