加强网站的建设工作,公司管理系统cms,建设运营网站,app和小程序的区别你是一名宇航员#xff0c;即将前往一个遥远的行星。在这个行星上#xff0c;有许多不同类型的矿石资源#xff0c;每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球#xff0c;但你的宇航舱有一定的容量限制。
给定一个宇航舱#xff0c;最大容量为 C。现在…你是一名宇航员即将前往一个遥远的行星。在这个行星上有许多不同类型的矿石资源每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球但你的宇航舱有一定的容量限制。
给定一个宇航舱最大容量为 C。现在有 N 种不同类型的矿石每种矿石有一个重量 w[i]一个价值 v[i]以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下最大化你所能获取的总价值。
输入描述
输入共包括四行第一行包含两个整数 C 和 N分别表示宇航舱的容量和矿石的种类数量。
接下来的三行每行包含 N 个正整数。具体如下
第二行包含 N 个整数表示 N 种矿石的重量。
第三行包含 N 个整数表示 N 种矿石的价格。
第四行包含 N 个整数表示 N 种矿石的可用数量上限。
输出描述
输出一个整数代表获取的最大价值。
输入示例
10 3
1 3 4
15 20 30
2 3 2
输出示例
90
提示信息
数据范围 1 C 10000; 1 N 10000; 1 w[i], v[i], k[i] 10000; #includeiostream
#includevector
using namespace std;int c,n; // 容量 和 种类数量
void chose(){vectorintweight(n);vectorintvalue(n);vectorintnums(n);for(int i 0;i n;i){cin weight[i];}for(int i 0;i n;i){cin value[i];}for(int i 0;i n;i){cin nums[i];}/*多重背包嵌套的01背包5个种类的物品每个种类又各有几件。例如 1 15 22 30 23 20 3将件数展开1 15 11 15 12 30 12 30 13 20 13 20 13 20 1这就是一个标准的01背包每一次只能取一个。 *///将物品展开。 对于c来说如果需要添加的物品很多那么vector动态扩容非常耗费时间 //优化版本就是不做展开操作而是在dp遍历的时候多加一个循环遍历件数 /*for(int i 0;i n;i){while(nums[i] 1){weight.push_back(weight[i]);value.push_back(value[i]);nums[i]--;}} *///此时已经转化为一个标准的01背包vectorintdp(c1,0);for(int i 0;i n;i){for(int j c;j weight[i];j--){for(int k 0;k nums[i] (j - k*weight[i]) 0;k){dp[j] max(dp[j], dp[j-k*weight[i]] k*value[i]);}}} cout dp[c] endl;
}int main(){cin c n;chose();return 0;
}
