湖南省建设信息网站,聊城做网站厉害的公司,网站最重要的是首页吗,做网站用什么字体最明显题意
N个物品每个就一个给出每个物品的价值和花费#xff0c;表示最终选择一些物品使得花费不超过M#xff0c;使得价值最大化
分析
最优化问题 考虑dp n个物品选择一些得到最后的最优化问题 我们不妨考虑#xff0c;假设我们得到了n-1个物品在容量为m情况下最优化值存…题意
N个物品每个就一个给出每个物品的价值和花费表示最终选择一些物品使得花费不超过M使得价值最大化
分析
最优化问题 考虑dp n个物品选择一些得到最后的最优化问题 我们不妨考虑假设我们得到了n-1个物品在容量为m情况下最优化值存储在fn-1,m中 当前关于第n个物品我们考虑最优值 选或者不选 也就是需要对比f(n-1,m)f(n-1,m-w[n])d[i]的大小 为最优解的结构 由于前者是不选 而后者表示选就需要给第n个物品腾出w[n]的大小情况下的价值 也就是在n-1个物品有m-w[n]容量下的最大价值得到 再加上d[i]为最终的价值 所以这种选择方案的意义在于 对于一个新的物品 我们选还是不选 是根据前面的状态决定的 也就是说 不选那么前面数量以及容量下得到的最优值 和选的话 需要找到有足够的空间下得到的最优值哪个更优 对每个物品做如上操作 所以对于n-1规模的子问题 我们需要递归处理 最终还是先解决f(1,m)的所以我们不如自底向上地去计算值 滚动数组搞一下 最终存储在m下标下的就是解 剩下的就是编写代码和计算了
code
#includecstdio
#includealgorithm
using namespace std;
int w[3500],d[3500],dp[12883];int main()
{int n,m;scanf(%d%d,n,m);for(int i1;in;i)scanf(%d%d,w[i],d[i]);for(int i1;in;i){for(int jm;jw[i];j--){dp[j] max(dp[j],dp[j-w[i]]d[i]);}}printf(%d\n,dp[m]);return 0;
}
