行业网站做的好的,网站内链如何做优化,商务网站开发考卷,单位网站建设情况调查情况文章目录1. 题目2. 解题1. 题目
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件#xff0c;每件体积是 vi#xff0c;价值是 wi。
求解将哪些物品装入背包#xff0c;可使物品体积总和不超过背包容量#xff0c;且价值总和最大。 输出最大价值。
输入格式…
文章目录1. 题目2. 解题1. 题目
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式 输出一个整数表示最大价值。
数据范围 0N≤1000 0V≤2000 0vi,wi,si≤2000 提示 本题考查多重背包的二进制优化方法。
输入样例 4 5 1 2 3 2 4 1 3 4 3 4 5 2
输出样例 10
题目来源https://www.acwing.com/problem/content/description/5/
2. 解题
本题是在 4. 多重背包问题 I 的基础上加大了数据规模直接用上一题的代码是没问题的但是时间复杂度很高会超时
将 si 拆分成 1,2,4,8, … ,2^k, 剩余的数这些数每个数表示一个新的物品这个新的物品是原来的n个组合成的这些数可以组合成 1 - si 的任意数然后应用 01 背包解决问题时间复杂度 O(NVlogS)O(NV \log S )O(NVlogS)空间复杂度 O(V)O(V)O(V)
#includebits/stdc.h
using namespace std;int main()
{int N, V, vi, wi, si, maxprice 0;cin N V;vectorint dp(V1, -1);dp[0] 0;// dp[v] 表示体积为 v 时装的最大价值for(int i 0; i N; i){cin vi wi si;for(int k 1; si k; k*2)//二进制拆分{int price wi*k;//合并成一个物品其价值int v vi*k;//其体积si - k;//剩余物品数量for(int j V-v; j 0; --j)// 01 背包状态更新{if(dp[j] -1)//状态不存在continue;dp[jv] max(dp[jv], dp[j]price);maxprice max(maxprice, dp[jv]);}}if(si 0)//还剩余的单独打包成一个物品{int price wi*si;int v vi*si;for(int j V-v; j 0; --j)// 01 背包状态更新{if(dp[j] -1)//状态不存在continue;dp[jv] max(dp[jv], dp[j]price);maxprice max(maxprice, dp[jv]);}}}cout maxprice endl;return 0;
}855 ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
