[poj2184]我是来水一下背包的

http://poj.org/problem?id=2184

题意:01背包的变种,就是说有2组值(有负的),你要取一些物品是2阻值的和非负且最大

分析:

1、对于负的很好处理,可以把他们都加上一个数使其变成正数

2、对于两个变量可以控制一个变量,求另一个变量的最大值,那么接下来的问题就是处理“体积恰好为V的01背包”问题了(和普通的不同哦……普通的不一定装满的)

以前处理恰好体积为V的01背包都是开数组染色刷一遍的,原来有更好的方法,就是初始值是f[0]=0,f[1..V]=-inf,那么转移中f[j]=f[j-v[i]]+w[i],若j-v[i]表示的背包没有装满那么这个就不能转移了……真心有点机智……Mark一下

原文地址:https://www.cnblogs.com/wmrv587/p/3587153.html