我正在学习动态编程，我解决了几个DP问题，但我发现这个问题对我的水平来说相当困难。对我来说，这个问题比简单的活动选择要困难得多。
因此，给定每个活动中有 N 个活动的成本，选择最大活动，您不能花费超过 M 的金额。
1<=N，M<=10^5 1<=开始 <= 结束 <=10^5 1<=成本 <= 10^5 例如，我们有 5 个活动和 11 个钱 格式：从-到->成本 1-3 -> 5 1-5 -> 9 4-6 -> 6 5-6 -> 1 6-10 -> 1 1-5，
5-6，
6-10 = 9 + 1 +1 = 11
因此，答案是 3 活动
当然， 如果有另一个答案具有相同的最大活动量：1-3、5-6、6-10，因此您可以选择所需的任何答案。
这是我的代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct temp{
int from;
int to;
int cost;
};
using data = vector<temp>;
int f(data a, int len, int m){
if (len<0 || m<0) return 0;
int val=0;
for (int i=0; i<len; i++){
if (a[len].from >= a[i].to)
val=max(val,f(a,len-i-1,m-a[len].cost)+1);
else
val=max(val,f(a,len-i-1,m)+1);//try another activity
}
return val;
}
int main(){
data activity;
int n,m;
cin >>n >> m;
for (int i=0; i<n; i++){
int a,b,c;
cin >> a >> b >> c;
activity.push_back({a,b,c});
}
cout << f(activity,activity.size()-1,m);
}
我的代码有什么问题？我知道有几件事是错误的，但我不知道在哪里。如何修复递归中的错误？ 另外，如果可能的话，你能使算法更快吗？无需更改为自下而上的方法
我觉得这是加权活动问题和背包问题的混合问题。 这很困难，但非常有趣，是一个很好的学习机会。 我提出一个DP。方法在下面的帖子中。 如果我弄错了什么，请有人纠正我。 然后我希望进行建设性的讨论。
方法
首先，我们将活动标记为A = {a1, a2, .., aN}并按完成时间对它们进行排序，如下所示：
|----|a1
|-----|a2
|-------|a3
|-----|a4
....
下一个
让
S(A,M)成为具有数量MA活动的最佳解决方案。让
L(a)A的所有活动严格地放在元素的左侧a的A.example.) |----|a1 |-----|a2 L(a4)={a1, a2} |-------|a3 |-----|a4 ....
我们可以搜索S(A,M)从最左边的活动a1开始，然后到最右边的活动aN。 对于每个活动ai，我们可以将其左区域视为L(ai)。
如果M是无穷大的，则在第i步中，S(L(ai),M)和ai的并集是最优解的候选者。因此，子问题是S(L(ai),M)。 在此步骤中，我们已经有S(a1,M)，S({a1,a2},M),...,S({a1,...,a_i-1},M). 由于a1,...,aN是按其完成时间排序的，因此我们可以将其S(L(ai),M)为其中之一或其中一些。 这种递归方法是当前问题的起点。
example.) M=infinity
|----|(a1,cost=2) subproblem of 1st step: S(L(a1),M)=empty
|---|(a2,1) subproblem of 2nd step: S(L(a2),M)={a1}
|----|(a3,2) subproblem of 3rd step: S(L(a3),M)={a1,a2}
|--------|(a4,4) subproblem of 4th step: S(L(a4),M)={a1,a2}=S(L(a3),M)
.... ^^^^^^^^^^ cached!
如果M是有限的，则S(L(ai),M-cost(ai))和ai的并集是最优解的候选者。因此，我们必须解决的不是S(L(ai),M)而是S(L(ai),M-cost(ai))。 在这种情况下，不一定缓存每个步骤中的子问题。
example.) M=5
|----|(a1,2) subproblem of 1st step: S(L(a1),3)=empty
|---|(a2,1) subproblem of 2nd step: S(L(a2),4)={a1}
|----|(a3,2) subproblem of 3rd step: S(L(a3),3)={a1,a2}
|--------|(a4,4) subproblem of 4th step: S(L(a4),1)={a2}!=S(L(a3),3)
.... ^^^^^^^^ uncached!
因此，在具有无限M的标准加权活动选择问题的情况下，我们总是可以专注于活动最活跃的组合。 但是在当前有限M问题中，我们必须缓存各种成本低于递归步M的组合。
实现
记忆
适当的缓存表结构会有所不同，具体取决于是否M无限。 如果M是无限的，则一维缓存表足以执行动态规划。 但是如果M是有限的，我们需要二维缓存表。在您的示例中，它变为如下：
end
3 4 5 6 10 <= end
1 | | | | [5,6] | [5,6],[6,10] |
2 | | | | [5,6] | [5,6]+[6,10] |
money 3 | | | | [5,6] | [5,6]+[6,10] |
4 | | | | [5,6] | [5,6]+[6,10] |
5 |[1,3]|[1,3]|[1,3]|[1,3],[5,6]| [5,6]+[6,10] |
6 |[1,3]|[1,3]|[1,3]|[1,3]+[5,6]|[1,3]+[5,6],[1,3]+[6,10],[5,6]+[6,10]|
... ...
因此，我定义以下缓存表类CacheTable：
缓存表
std::map<std::pair<to,money>,Activities>> table_缓存S({a|a of A, a<=to},money)的元素。CacheTable::operator()用于访问缓存表。CacheTable::getCachedOptimal用于在完成时间和金钱的限制下从缓存的结果中找到最佳解决方案。
我的快速实现如下：
struct activity
{
std::size_t from;
std::size_t to;
std::size_t cost;
};
using Activities = std::vector<activity>;
class CacheTable
{
// (to,money) --> cached optimal activities
std::map<std::pair<std::size_t,std::size_t>, Activities> table_;
public:
Activities& operator()(std::size_t to, std::size_t money)
{
auto key = std::make_pair(to, money);
auto it = table_.find(key);
if(it == table_.cend()){
it = table_.emplace_hint(it, std::move(key), Activities());
}
return it->second;
}
Activities getCachedOptimal(std::size_t to, std::size_t money) const
{
Activities cachedOptimal;
for(auto it = table_.begin(); it != table_.cend(); ++it)
{
if((it->first.first <= to) && (it->first.second <= money))
{
if(it->second.size() > cachedOptimal.size()){
cachedOptimal = it->second;
}
}
}
return cachedOptimal;
}
};
求解
使用上面的缓存表，我们可以实现当前问题的DP.求解器，如下所示。 此求解器只能找到S(A,M)的单个元素。演示在这里。 虽然这应该有效，但我认为有更有效的方法来解决这个问题。
class DPSolver
{
Activities activities_;
mutable CacheTable cacheTable_;
Activities impl(std::size_t from, std::size_t to, std::size_t money) const
{
if((from >= to) || (money == 0)){
return {};
}
const auto cache = cacheTable_(to, money);
if(!cache.empty()){
return cache;
}
for(const auto& act_i : activities_)
{
if((act_i.to <= to) && (money >= act_i.cost))
{
const auto remaining = (money - act_i.cost);
auto acts = impl(from, act_i.from, remaining);
const auto thisCost = calcCost(acts) + act_i.cost;
const auto found = cacheTable_.getCachedOptimal(act_i.to, thisCost);
if(found.size() < (acts.size()+1))
{
acts.push_back(std::move(act_i));
cacheTable_(act_i.to, thisCost) = acts;
}
}
}
return cacheTable_.getCachedOptimal(to, money);
}
public:
DPSolver(const Activities& activities) : activities_(preprocess(activities))
{}
static Activities preprocess(const Activities& activities)
{
auto sorted(activities);
// preprocessing to order by finished time "to".
std::sort(
sorted.begin(), sorted.end(),
[](const activity& al, const activity& ar)
{ return std::tie(al.to, al.from, al.cost) < std::tie(ar.to, ar.from, ar.cost); });
return sorted;
}
static std::size_t calcCost(const Activities& activities)
{
return std::accumulate(
activities.cbegin(), activities.cend(), 0,
[](int sum, const activity& a){ return sum + a.cost;});
}
Activities operator()(std::size_t from, std::size_t to, std::size_t money) const
{
// clear cache table
cacheTable_ = CacheTable();
return impl(from, to, money);
}
};