dp(8) 1282:【提高】简单背包问题

1282:【提高】简单背包问题

链接：1282 - 简单背包问题-东方博宜OJ

题目：1282:【提高】简单背包问题

题目描述

有一个背包能装的重量 maxwmaxw (正整数，0≤maxw≤200000≤maxw≤20000)，同时有 nn 件物品(1≤n≤1001≤n≤100)，每件物品有一个重量 wiwi​ (正整数)和一个价值 pipi​ (正整数)。要求从这 nn 件物品中任取若干件装入背包内，使背包的物品价值最大。

输入

第 11 行：背包最大载重 maxwmaxw，物品总数 nn ；

第 22 行到第 n+1n+1 行：每个物品的重量和价值；

输出

一个数字即背包内物品最大价值；

样例

输入

复制

10 3 4 5 3 4 6 9

输出

复制

14

来源

动态规划 背包问题

标签