这件事情的起因是在学习背包问题时突然想到了一种算法, 分析了一下应该是 n^2logn 复杂度的, 当然比 dp 慢. 但是既然想到了就实现了下:
- #include<bits/stdc++.h>
- using namespace std;
- typedef unsigned long long ll;
- /* 一个很低效的方法, 但是是自己想到的, 就顺手实现了一下. 本质是基于穷举法的优化, 不再循环所有物品选取的组合, 而是循环状态.
- 大致地看, 其一定是比穷举法要快些的, 因为其合并了穷举法的许多情况, 即处于 "现在背包中物品的总价值相同且剩余空间相同" 的不同物品选取情况.
- 但是其的复杂度至少是 n^2*logn 级别的, 因为其需要对每一个物品循环 set 中的元素并不断插入新的状态, 而且还涉及到了类的存储, 速度应该会更慢一些 */
- class stateNow{
- public:
- int sizeRest;
- int valueAll;
- bool operator <(const stateNow& te)const{
- if((this->sizeRest<te.sizeRest)||(this->sizeRest==te.sizeRest&&this->valueAll>te.valueAll))
- return true;
- else
- return false;
- }
- };
- int main(){
- int n,size;
- scanf("%d %d",&n,&size);
- int *objectSize=new int[n];
- int *objectValue=new int[n];
- set<stateNow>::iterator it;
- set<stateNow>stateCollection;
- int maxValue=0;
- for(int i=0;i<n;i++){
- scanf("%d %d",&objectSize[i],&objectValue[i]);// 不能把 \ n 也加到字符串里,\n 是输入结束的标志, 将它也读入的话会影响结束
- }
- for(int i=0;i<n;i++){
- if(!stateCollection.empty()){
- for(it=stateCollection.begin();it!=stateCollection.end();it++){
- stateNow temp;
- temp.sizeRest=it->sizeRest-objectSize[i];
- temp.valueAll=objectValue[i]+it->valueAll;
- if(temp.sizeRest==0){
- if(temp.valueAll>maxValue)
- maxValue=temp.valueAll;
- }
- if(temp.sizeRest>0)
- stateCollection.insert(temp);
- }
- }
- stateNow temp;
- temp.sizeRest=size-objectSize[i];
- temp.valueAll=objectValue[i];
- stateCollection.insert(temp);
- }
- printf("%d",maxValue);
- getchar();
- }
- }
这里就涉及到了一个向 set 中传入自定义类型的问题, 查到了一篇博文, 正好在讲这个问题, 这里就不引用原文了, 大家直接点击链接看吧:
为什么需要定义比较函数对象或者自定义 < 运算符呢? 因为 set 内部是有序排列的 (红黑树), 并且要保证元素的唯一性, 所以需要一个能用来比较两元素的方法.(two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false.)
另外, 由博文中所说, 总是让比较函数使被比较对象满足严格的弱序, 即
严格弱序化拥有如下属性. 对于集合 S 中所有的 x,y,z,
对于所有的 x, 不存在 x < x (非自反性 - 21 条标题说的就是这个)
对于所有 x 不等于 y, 如果 x < y 那么不存在 y < x (不对称性)
对于所有的 x,y 和 z, 如果 x < y 并且 y < z, 那么 x < z(传递性)
如果 x < y, 那么对于所有的 z, 要么 x < z 要么 z < y(或者两者都成立)
这一点在自定义 < 运算符时要注意, 否则所进行的操作就是未定义行为, 会出现意料之外的错误.
来源: http://www.bubuko.com/infodetail-3108735.html