首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

动态规划——多重背包

多重背包区别于01背包和完全背包的关键是,物品的个数一定。 但它们的状态方程还是一样的,对于多次背包问题,我们可以把他转换成01背包问题,但是要注意优化,因为当数据量比较大的时候,容易费时,即时间复杂度太高,需要进行优化。 我们先把之前的状态方程在· f[i][j]表示从i个物品中选取体积不超过j物品的最大价值。 f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,........,f[i-1][j-kv]+kw),kv<j。 这时读者朋友可能会想可不可以像完全背包那样,进行状态方程的转换。emmm,答案是:不可以的,不信的话可以自己尝试转换一下。 下面我们用01背包的思想去解决该问题,对于i个物品有k个,价值为w;那么我们可不可以把它这样理解:我们把这些物品都看成不一样的,再仔细想一下,这不就变成01背包了吗?但是时间太慢了,我们优化一下。 这里的优化为二进制优化 我们把这k个物品进行分割处理, 分为1,2,4,8,16………。只要保证其和大于k就可以。 为什么空2进制来优化呢,因为可以减少时间复杂度,其他0到k之中的任意一个数都可以由分割的二进制数进行组合而成。 例如:k为25,下面进行分割 1,2,4,8,16.怎么分割的呢? 先是1,那么还剩24 2,22 4,28 8,20 16,4 4,0//剩余的自己组成一个 剩下就是01背包了,注意此时不再有i个物品了,而是变成了转换以后的物品个数。

04

BestSync同步软件 同步 VM 虚拟机里的Linux系统下Tomcat webapps里的项目

首先,这篇文章也不知道对别人有没有用,源于我在虚拟机安装Linux,部署Tomcat项目时,为了避免当项目发生改变时,一次次重复的上传项目,因此我想可不可以把本地Tomcat 的 webapps 目录跟 虚拟机 tomcat webapps 目录 同步一下,这样当我更新本地 svn 后,把webapps用软件同步 到 linux (软件只同步改动的文件),这样做可以避免把整个项目上传到 linux (我这有好几个项目,因为你更新svn了,如果只是自己改动了,可以仅把自己的拷到 linux,但是其他人改了什么你并不知道,或者说还要一个个找,只能把整个项目传到 虚拟机),然后我就在网上找了下 同步软件,发现 BestSync 这个同步软件很好用,下面就说一下具体用法。

02
领券