蒜头君的购物袋3 |
您所在的位置:网站首页 › hm购物袋可以承重多少 › 蒜头君的购物袋3 |
1.题目
蒜头君去超市购物,他有一只容量为 V 的购物袋,同时他想买 nn 种物品,已知每种物品的体积 vi和重要度 pi 。蒜头君想知道,怎么挑选物品放入购物袋中,可以使得买到的物品重要度之和最大,且物品体积和不超过购物袋的容量。注意超市中每种物品的数量无限多。 输入格式 第一行输入两个整数 n, V (1≤n≤1,000,1≤V≤10,000)。 接下来输入 n 行,每行输入两个整数 vi和pi(1≤vi,pi≤10,000),分别表示第 i 种物品的体积和重要度。 输出格式 输出一行,输出一个整数,表示能买到物品的最大重要度之和。 2.分析核心代码:for(int j=v[i];j for(int j=v[i];j=v[i];j++)//01背包就可以这样,就差一丢丢,巧妙啊, */ dp[j]=max(dp[j-v[i]]+p[i],dp[j]);//模拟一遍你就明白啥意思了,太ji er巧妙了 } cout |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |