2 条题解
-
1
上代码
#include<bits/stdc++.h> using namespace std; int n,m,ans,cnt=1,f[1000001],w[1000001],v[1000001],a,b,c; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a>>b>>c; for(int j=1;j<=c;j<<=1){ v[++cnt]=j*a; w[cnt]=j*b; c-=j; }if(c){ v[++cnt]=a*c; w[cnt]=b*c; } }for(int i=1;i<=cnt;i++)for(int j=m;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+v[i]); cout<<f[m]; return 0; }
-
0
欢迎访问我的博客:blog.chungzh.cn
题意
终于,破解了千年的难题。小 FF 找到了王室的宝物室,里面堆满了无数价值连城的宝物。
这下小 FF 可发财了,嘎嘎。但是这里的宝物实在是太多了,小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。
小 FF 对洞穴里的宝物进行了整理,他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值,之后开始了宝物筛选工作:小 FF 有一个最大载重为 的采集车,洞穴里总共有 种宝物,每种宝物的价值为 ,重量为 ,每种宝物有 件。小 FF 希望在采集车不超载的前提下,选择一些宝物装进采集车,使得它们的价值和最大。
对于 的数据,,,。
解法 1:二进制优化
每一个数都可以表示成 的幂的和(因为每一个数都可以用二进制表示)。
时间复杂度:
#include <bits/stdc++.h> using namespace std; int dp[40005]; int main() { int n, W; scanf("%d%d", &n, &W); for (int i = 0; i < n; i++) { int t, c, p; scanf("%d%d%d", &c, &t, &p); int tmp = 1; while (p >= tmp) { p -= tmp; for (int j = W; j >= t*tmp; j--) dp[j] = max(dp[j], dp[j-t*tmp]+c*tmp); tmp *= 2; } if (p == 0) continue; for (int j = W; j >= t*p; j--) { dp[j] = max(dp[j], dp[j-t*p]+c*p); } } printf("%d\n", dp[W]); return 0; }
解法 2:单调队列优化
设 表示前 种物品重量不超过 的最大价值。显然有一个状态转移方程:
$$f[i][j] = max_{0<=k<=m[i]}\{f[i-1][j-k\times w[i]]+k\times v[i]\} $$我们设 :
$$f[i][j]=max\{f[i-1][(k_1-k)\times w[i]+d]-(k_1-k)\times v[i] \}+ k_1\times v[i] $$我们枚举余数 和 ,就可以表示出每一个数,然后维护一个单调队列,这个队列里面的决策通过加上第 种物品都可以凑成 ,因此增加的数量不能超过 ,也就是 。
时间复杂度:
#include <bits/stdc++.h> using namespace std; int n, W; int v[105], w[105], m[105]; int dp[105][40004]; struct deq { int head, tail; int arr[40004]; bool empty() { return head+1 == tail; } void pop_front() { head++; } void pop_back() { tail--; } void push_back(int x) { arr[tail] = x; tail++; } void clear() { head = 0; tail = 1; } int front() { return arr[head+1]; } int back() { return arr[tail-1]; } } dq; int main() { cin >> n >> W; int ans = 0; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i] >> m[i]; if (w[i] == 0) { ans += v[i]*m[i]; continue; } for (int j = 0; j < w[i]; j++) { // 余数 dq.clear(); // k 实际上表示的是文中的 k_1 for (int k = 0; j+k*w[i] <= W; k++) { // dq.front() 实际上表示的是文中的 k_1 - k while (!dq.empty() && k-dq.front() > m[i]) dq.pop_front(); while (!dq.empty() && dp[i-1][j+dq.back()*w[i]]+(k-dq.back())*v[i] <= dp[i-1][j+k*w[i]]) dq.pop_back(); dq.push_back(k); if (!dq.empty()) dp[i][j+k*w[i]] = max(dp[i][j+k*w[i]], dp[i-1][j+dq.front()*w[i]]+(k-dq.front())*v[i]); } } } cout << dp[n][W]+ans << endl; return 0; }
- 1
信息
- ID
- 745
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 4
- 标签
- 递交数
- 29
- 已通过
- 12
- 上传者