【题目描述】

一个旅行者有一个最多能装 m 公斤物品的背包，现在有 n 件物品，它们的重量分别是 w1,w2,…,wn, 它们的价值分别为 c1,c2,…cn 。若每种物品只有一件，求旅行者能获得的最大总价值。

【输入】

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

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

【输出】

一个数据，表示最大总价值。

【输入样例】

10 4  2 1  3 3  4 5  7 9

【输出样例】

12

【题目分析】

1. 比较典型的贪心算法，
   
   

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