基于动态规划的有限资金活动选择
我正在学习动态编程，我解决了几个DP问题，但我发现这个问题对我的水平来说是相当困难的。对我来说，这个问题比简单的活动选择困难得多。
因此，如果每个活动中有成本的N个活动，选择最大的活动，你不能花费超过M的钱。
1<=N，M<=10^5
1<=start <= end <=10^5
1<=Cost <= 10^5
例如，我们有5项活动和11项资金
格式：
From-To ->
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);
}我的密码怎么了？我知道有几件事是错的，但我不知道在哪里。如何修复递归中的错误？此外，如果可能的话，你能使算法更快吗？而不更改为自下而上的方法
回答 1
Stack Overflow用户
发布于 2018-10-30 20:01:30
我觉得这是一个加权活动问题和背包问题的混合问题。这是困难的，但非常有趣和一个伟大的学习机会。我提议一个DP。方法在下面的文章中。如果我弄错了，请有人纠正我。然后，我希望有一个建设性的讨论。
方法
首先，我们将活动标记为A = {a1, a2, .., aN}，并按完成时间对它们进行排序，如下所示：
|----|a1
|-----|a2
|-------|a3
|-----|a4
....下一首,
- 让
S(A,M)是活动A的最优解，A的数量为M。 - 让
L(a)严格地在元素aofA的左侧是A的所有活动。 )(例子：
我们可以从最左边的Activitya1开始搜索S(A,M)，然后继续搜索最右边的ActivityaN。对于每个活动ai，我们可以考虑它的左区域L(ai)。
如果M 是无限，则在i-th步长中，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的各种组合。
实现
Memorization
适当的缓存表结构是不同的，这取决于是否存在无限的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);
}
};https://stackoverflow.com/questions/52255798
复制相似问题
腾讯云开发者
