我被这个问题困扰了几天-
Consider a modification to the activity-selection problem in which each activity ai has, in addition to a start and finish time, a value vi. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set A of compatible activities such that summation of their corresponding values is maximized. Give a polynomial-time algorithm for this problem.
我知道这个问题已经得到回答here &我设计了一种 DP 方法来找出值的总和。但是您可以打印所选的事件吗?
最佳答案
C++代码如下。希望您能轻松地将其翻译成任何其他语言。
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000
struct activity
{
int start;
int finish;
int weight;
};
bool comp(activity m, activity n)
{
return m.finish>n.finish;
}
int dp[N];
int main()
{
int n, maxi=-1;
int DP[N];
activity a[N];
scanf("%d", &n);
for(int i=0;i<n;i++)
{
scanf("%d %d %d", &a[i].start, &a[i].finish, &a[i].weight);
a[i].pos=i+1;
}
sort(a, a+n, comp);
for(int i=0; i<n; i++)
dp[i]=a[i].weight;
for(int i=1; i<n; i++)
{
for(int j=0; j<i; j++)
{
if(a[j].finish<=a[i].start)
dp[i]=max(dp[i], dp[j]+a[i].weight);
maxi=max(dp[i], maxi);
}
}
printf("%d\n", maxi);
int act[N];
int k=0;
for(int i=n-1;i>=0;i--)
{
if(dp[i]==maxi)
{
maxi-=a[i].weight;
act[k++]=a[i].pos;
}
}
for(int i=k-1;i>=0;i--)
printf("%d ", act[i]);
return 0;
}
关于algorithm - 加权事件选择,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39693094/