加權活動選擇

Question

我堅持這個問題幾天 -

考慮修改該活動的選擇問題，其中每個活動_我有，除了開始和結束時間，值v _i。目標不再是最大限度地安排活動的數量，而是最大限度地提高活動的總價值。也就是說，我們希望選擇兼容活動的集合，使得它們的相應值的總和被最大化。給出一個多項式時間算法 這個問題。

我知道這個問題已經回答了here &我設計了一個DP的方法來找出值的總和。但你能打印選擇的活動？

Answer 1

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; 
}