CODEVS 3269 混合背包

 2023-09-05 阅读 272 评论 0

摘要:一道裸的混合背包题目。可是忘记了去重一直TLE,就是假设体积<=全然背包的01。和多重背包都要被全然背包代替,由于他的数量没限制所以用起来更方便。 题目连接:http://codevs.cn/problem/3269/ #include <iostream> #include <string.h&

一道裸的混合背包题目。可是忘记了去重一直TLE,就是假设体积<=全然背包的01。和多重背包都要被全然背包代替,由于他的数量没限制所以用起来更方便。

题目连接:http://codevs.cn/problem/3269/

#include <iostream>
#include <string.h>
#include <cstdio>
#include <cstdlib>
using namespace std;const int maxn = 210;
const int maxc = 200010;inline int read()
{char ch;bool flag = false;int a = 0;while(!((((ch = getchar()) >= '0') && (ch <= '9')) || (ch == '-')));if(ch != '-'){a *= 10;a += ch - '0';}else{flag = true;}while(((ch = getchar()) >= '0') && (ch <= '9')){a *= 10;a += ch - '0';}if(flag){a = -a;}return a;
}
void write(int a)
{if(a < 0){putchar('-');a = -a;}if(a >= 10){write(a / 10);}putchar(a % 10 + '0');
}int f[maxc], v[maxn], w[maxn], m[maxn];
int n, V;
bool vis[maxn];void complete_pack(int cost, int weight)
{for(int j = cost; j <= V; j++)f[j] = max(f[j], f[j-cost]+weight);
}void zero_pack(int cost, int weight)
{for(int j = V; j >= cost; j--)f[j] = max(f[j], f[j-cost]+weight);
}void multi_pack(int cost, int weight, int amount)
{if(cost*amount >= V){complete_pack(cost, weight);return;}int k = 1;while(k < amount){zero_pack(cost*k, weight*k);amount -= k;k <<= 1;}zero_pack(amount*cost, amount*weight);
}
int main()
{n = read();V = read();memset(vis, false, sizeof(vis));for(int i=1; i<=n; i++){v[i] = read();w[i] = read();m[i] = read();}for(int i = 1; i <= n; i++){for(int j = i+1; j <= n; j++){if(m[i] == 1){if(m[j] == -1)if(v[i] >= v[j] && w[i] <= w[j]) vis[i] = true;if(m[j] > 1)if(v[i] >= v[j] && w[i] <= w[j]) vis[i] = true;}else if(m[i] > 1){if(m[j] == -1)if(v[i] >= v[j] && w[i] <= w[j]) vis[i] = true;}}}for(int i=1; i<=n; i++){if(m[i]==1 && !vis[i])zero_pack(v[i], w[i]);else if(m[i]==-1)complete_pack(v[i], w[i]);else if(!vis[i])multi_pack(v[i], w[i],m[i]);}write(f[V]);return 0;
}


转载于:https://www.cnblogs.com/clnchanpin/p/6897928.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/1/659.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息