一个增多条件的背包算法

一个增加条件的背包算法


每个小格有个权值（设为Ai （0 < i <= n）），表示选取后将获利多少。
（白色的表示没被选取，黄色的表示选取了）

背包大小有限为Msize，小格每个大小是m,总共n格，m*n > Msize

选取的小格的段数越多代价越高，每一段（不连续的黄色为一段）的代价是vh。

最后求一个最大的获利

MAX = （Ai  + Ak …… Aj） - vh * （段数）

并且  mi + mk + …… Aj < Msize



[解决办法]

引用:

引用:定义dp[i][j][2]表示 前i个格子，选择j个的最大获利
最后一维0表示 不选第i个（白色）  1表示 选择第i个

dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);
dp[i][j][1]=max(dp[i-1][j-1][0]+ai-vh,dp[i-1][j][1]+ai)
……

- -
[解决办法]
我说的办法解决不了么
[解决办法]
mi + mk + …… Aj < Msize

看到你这句，我就觉得你写在这里的题意可能不是你想表达的意思。
[解决办法]
>背包大小有限为Msize，小格每个大小是m,总共n格，m*n > Msize
那m和mi有啥区别
[解决办法]
>m*n > Msize
那你每小格的m到底是一样的还是不一样的？一样的话那这句什么意思？

查看更多 下一篇