【题目描述】

设有 n 中物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为 m ，今从 n 种物品中选取若干件（同一物品可以多次选取），使其重量的和小于等于 m ，而价值的和为最大。

【输入】

第一行：两个整数， m （背包容量， m ≤ 200 ）和（物品数量， n ≤ 30 ）；

第二 行~到n+1 行：每行两个整数 wi ， ui ，表示每个物品的重量和价值。

【输出】

仅一行，一个数，表示最大总价值。以max=开头。

【输入样例】

10 4  2 1  3 3  4 5  7 9

【输出样例】

max=12

(adsbygoogle = window.adsbygoogle || []).push({});