// Weighted interval scheduling. See Kleinberg & Tardos, chapter 6 // Finds solution using powerset enumeration. 10/08/11 BPW #include #include #define TABSIZE (31) // Due to powerset size int n,s[TABSIZE],f[TABSIZE],v[TABSIZE],p[TABSIZE]; char subset[TABSIZE],subsetKeep[TABSIZE]; int max(int x,int y) { if (x>y) return x; return y; } int binSearchLast(int *a,int n,int key) { // Input: int array a[] with n elements in ascending order. // int key to find. // Output: Returns subscript of the last a element <= key. // Returns -1 if keyhigh, low==high+1 and a[high]<=key and a[low]>key. while (low<=high) { mid=(low+high)/2; if (a[mid]<=key) low=mid+1; else high=mid-1; } return high; } int main() { int i,j,sum,sumKeep; scanf("%d",&n); f[0]=(-999999); // For binarySearchLast for (i=1;i<=n;i++) scanf("%d %d %d",&s[i],&f[i],&v[i]); for (i=2;i<=n && f[i-1]<=f[i];i++) ; if (i<=n) { printf("Intervals not ordered by finish time %d\n",__LINE__); exit(0); } // p values are used to make overlap test simple. for (i=1;i<=n;i++) p[i]=binSearchLast(f,n+1,s[i]); // Start at empty set for powerset enumeration for (i=1;i<=n+1;i++) subset[i]=subsetKeep[i]=0; sum=sumKeep=0; while (1) { // Move to next subset using binary increment technique. // Complement the low-order ones and remove elements from next subset. for (i=1;subset[i];i++) { sum-=v[i]; subset[i]=0; } if (i==n+1) // All subsets enumerated? break; // Put new first (e.g. low-order one) element into the next subset. sum+=v[i]; subset[i]=1; // Assure that adjacent intervals do not overlap for (j=i+1;j<=n;j++) if (subset[j]) // Found adjacent interval { if (i<=p[j]) // No overlap i=j; // Move over to check next pair else break; // This subset has overlap for intervals i & j } if (j>n && sum>sumKeep) // No overlap and improvement { printf("Improvement to %d\n",sum); sumKeep=sum; for (i=1;i<=n;i++) subsetKeep[i]=subset[i]; } } printf(" i s f v p include\n"); for (i=1;i<=n;i++) { printf("%3d %3d %3d %3d %3d",i,s[i],f[i],v[i],p[i]); if (subsetKeep[i]) printf(" *"); printf("\n"); } printf("sum is %d\n",sumKeep); }