银川网站建设一条龙,网站被同行链接代替,太平洋在线建站系统,技术支持广州网站建设题目描述
小明是一位科学家#xff0c;他需要参加一场重要的国际科学大会#xff0c;以展示自己的最新研究成果。他需要带一些研究材料#xff0c;但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等#xff0c;它们各自占据不同的空间#xff0…题目描述
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料可以选择无数次并且可以重复选择。
输入
第一行包含两个整数NV分别表示研究材料的种类和行李空间
接下来包含 N 行每行两个整数 wi 和 vi代表第 i 种研究材料的重量和价值
输出
输出一个整数表示最大价值。
样例输入 复制
4 5
1 2
2 4
3 4
4 5
样例输出 复制
10
提示
第一种材料选择五次可以达到最大值。
数据范围
1 N 10000; 1 V 10000; 1 wi, vi 10^9.
#includeiostream
#includevector
using namespace std;int n,bagweight; // 种类 空间 void chose(){vectorintweight(n);vectorintvalue(n);for(int i 0;i n;i){cin weight[i] value[i];}//完全背包一个物品可以被拿n次所以是正序。 拓展先物品后背包是组合数即不允许集合重复。 先背包后物品是排列数顺序不一样也算//dp[j]:容量为j的背包最多可放dp[j]的价值vectorintdp(bagweight1);//递推关系dp[j] max(dp[j], dp[j-weight[i]] valu[i]);//初始化dp[0] 0for(int i 0;i n;i){for(int j weight[i];j bagweight;j){dp[j] max(dp[j], dp[j-weight[i]] value[i]);}} cout dp[bagweight];
}
int main(){cin n bagweight;chose();return 0;
}
