当前位置:首页 > 动态规划 > 01背包 > 正文
SSOJ2412完全背包
2195+

题目大意:n种物品放到一个载重量为m的背包,每种物品可以选多次,最多能装多大价值的物品?

题目描述

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

输入

第1行:两个整数,m(背包容量,m<=200)和n(物品数量,n<=30);

第2至n+1行:每行两个整数Wi,Ci,表示每个物品的重量和价值。

输出

仅一行,一个数,表示最大总价值。

样例输入

10 4
2 1
3 3
4 5
7 9

样例输出

max=12

解题思路

可以转成01背包来做:虽然每种物品可以选无限次,但总会有一个上限,如第一种物品,最多只能选m/wi次,再多就装不下了,时间复杂度O(m*∑(m/wi))。

由于容量可能很大,物品重量可能很小,这样物品数量就极大,可能远远超过n,造成超时。因此,我们可以采取更巧妙的方法,从小到大枚举容量(重量),如一个物品重量是2,那么求f[2]的时候用到f[0],求f[3]的时候用到f[1],求f[4]的时候用到f[2]……因为f[2]已经装过一次这个物品了,f[4]再装一次,相当于2次,如果后面又用到f[4],那么就是“多次选”、“无限次”了。

程序实现

About

坚决不Copy代码!

本文标签:,,,

SSOJ2412完全背包:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!