时间戳

首页 > 解决方案 > 使用自定义结构将结果存储在 C++ 中的映射中

c++ - 使用自定义结构将结果存储在 C++ 中的映射中

问题描述

我正在使用以下程序使用递归解决动态编程问题

#include <iostream>
#include <cmath>
#include <map>
#include <limits.h>
using namespace std;

int getMax(int a[], int start, int end){
    int i,m=0;
    for(i=start;i<end;i++){
        if(a[i]>m){
            m = a[i];
        }
    }
    return m;
}

int getanswer(int a[], int k,int prevstart, int start, int end, int total){
    if(start == end && k!=0){
        return INT_MAX;
    }
    else if(k == 1){
        return total + getMax(a,start,end);
    }
        
        return min(getanswer(a,k-1,start+1,start+1,end,total+getMax(a,prevstart,start+1)), getanswer(a,k,prevstart,start+1,end,total));
        
}

int main() {
    int a[] = {74303,20452,66120,44483,5370,68585};
    int  k = 5;
    cout<<getanswer(a,k,0,0,6,0);
    return 0;
}

它给出 234830 作为正确的输出。现在，我正在创建一个自定义结构并使用映射来存储结果。

#include <iostream>
#include <cmath>
#include <map>
#include <limits.h>
using namespace std;

struct Test { 
    int k;
    int prevstart;
    int start;
    int end;
}; 

bool operator<(const Test& t1, const Test& t2) 
{ 
    return (t1.k < t2.k) || (t1.k == t2.k && t1.prevstart < t2.prevstart) || 
    (t1.k == t2.k && t1.prevstart == t2.prevstart && t1.start < t2.start) ||
    (t1.k == t2.k && t1.prevstart == t2.prevstart && t1.start == t2.start && t1.end < t2.end); 
} 

map<Test,int> dp;
int getMax(int a[], int start, int end){
    int i,m=0;
    for(i=start;i<end;i++){
        if(a[i]>m){
            m = a[i];
        }
    }
    return m;
}

int getanswer(int a[], int k,int prevstart, int start, int end, int total){
    Test temp = {k,prevstart,start,end};
    if(dp.count(temp)){
        return dp[temp];
    }
    if(start == end && k!=0){
        return INT_MAX;
    }
    else if(k == 1){
        dp[temp] = total + getMax(a,start,end);
        return dp[temp];
    }
        
        dp[temp] = min(getanswer(a,k-1,start+1,start+1,end,total+getMax(a,prevstart,start+1)), getanswer(a,k,prevstart,start+1,end,total));
        return dp[temp];
}

int main() {
    int a[] = {74303,20452,66120,44483,5370,68585};
    int  k = 5;
    cout<<getanswer(a,k,0,0,6,0);
    return 0;
}

但是，现在它给出了 258861 作为输出。我怀疑我在重载 < 运算符时做错了什么。我在这里想念什么？

标签： c++dictionaryc++14dynamic-programming

解决方案

在第一个程序中，getanswer有时调用 , 的值相同，但k的值不同。因此它当然会返回不同的结果。prevstartstartendtotal

在第二个程序中，自然有时也会使用、和getanswer的相同值调用 is k，但. 但是，它从这些调用返回相同的结果 - 即，第一个此类调用计算并存储在映射中的结果。prevstartstartendtotal

推荐阅读