2744:01背包问题求具体方案

时间限制:2 S   /  内存限制:65536 KB
AC:12   /  Submit:42
问题描述

NN件物品和一个容量为MM的背包。

已知第ii件物品的重量是wiw_i,价值是viv_i

求解如何选取物品才能使装入背包的物品价值总和最大。

注意:每件物品至多选取11次!

输入描述

第一行是两个正整数M,NM,N分别代表背包的容量和物品的件数。(1M1051N1001 \le M \le 10^5,1 \le N \le 100

接下来NN行,每行两个正整数wi,viw_i,v_i分别表示第ii件物品的重量和价值。(1wi,vi1041 \le w_i,v_i \le 10^4

输出描述

在一行中输出可以使得装入背包的物品价值总和达到最大,且字典序最小的物品选取方案。

输出时,每两个数字之间用空格隔开,最后一个数字后面没有空格。

样例输入复制样例

5 4

1 2

2 4

3 4

4 6

样例输出

1 4

提示说明

“1 4” 和 “2 3” 都可以使得装入背包的物品价值总和达到最大,但是 “1 4” 字典序最小。

相关

题单#21(动态规划之背包DP)


Copyright 2016 - 2025 XUJC ACM Team
闽ICP备2020022076号-1