金字塔 (动态规划)

dp[i][j][k]前i个物品,选了j件,重量为k的最大价值

TLE

考虑消掉一维状态

由于第一个物品重量为0,所以可以先选出n+m个第一个物品,然后将其他物品的价值都减去第一个物品的价值

相当于将后面的物品分隔成了一个重量为0,价值为第一个物品的价值,和一个重量为其本身,价值为剩余价值的物品

这样就满足了选出N+M个物品的条件

于是问题转化成了在后n个物品中选出重量不超过n的物品的最大价值

因为选出k个物品的重量至少为k,所以数量限制是满足等于N+M的

原文地址:https://www.cnblogs.com/tuchen/p/10440187.html