题目链接：

方法：设一个数num，科目的数量为n,则将num表示成带有前导0的n位二进制数（num肯定不能超范围），在该二进制数的数位中，从左到有第i个数位是1代表第i门课的作业完成，0代笔没有，如n=4,num=6=0110代表第2和3门的作业完成，

设置状态转移方程，设F(num,k).Ans为 当完成k门课程，完成的科目是num对应的作业完成情况，这一状态下超期的最少天数。F(num,k).Beyond为 当完成k门课程，完成的科目是num对应的作业完成情况，这一状态已经超期的天数，F(num,k).Used 为 当完成k门课程，完成的科目是num对应的作业完成情况，这一状态已经使用的天数

 

F(num,k)=

{

　

　　[

　　Ans = Course[i].NeedDays - Course[i].DeadLine > 0 ?Course[i].NeedDays - Course[i].DeadLine :0 　,

　　Beyond = Ans,　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　

　　Used =  Course[i].NeedDays，　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　k==1, num in { 2^k| 1<=k<=n-1) };

　　

　　Pre = 0,

　　

　　Mask = num

　　]

 

　　

　　[

　　 Ans = Min(  

　　　　　　　　 　　{  

　　　　　　　　　　　　　　　　F(num1,k-1).Ans +( Course[J].NeedDays +F(num1,k-1).Used- Course[J].DeadLine > 0 ?Course[J].NeedDays+F(num1,k-1).Used - Course[J].DeadLine :0) 

　　　　　　　　　　　　　　　　|  num1 in {完成的k-1个作业的完成情况对应的状态二进制数} && num可以由num1的一个非1数位,第J位变成1获得 . 

　　　　　　　　　　　}      

　　　　　　　　  ),

　　　　

　　Beyond =  Ans,　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　Used =  Course[j].NeedDays+F(num1,k-1).Used ;这里的num1 和j 为上述Min计算选出的;　　　　　　　　　　　　　　　　　　　　k>1

　　

　　Pre = F(num1,k-1).Mask ; 这里的num1为上述Min计算选出的;

 

　　Mask = num1 ;这里的num1为上述Min计算选出的;

　　]　　　

　　　　　　　

}

 由于字段排序的要求，当判断一个数字状态num1是不是可以由一个已经算出结果的num通过一个非1数位,第J位变成1的到的时候，在找这样的一个第j位的时候，从左往右找即可。因为题目的输入就已经是字典有序的了。

在输入构造好的最有解的时候，就是纯粹模拟了。

代码：

#include 
     
      #include 
      
        using namespace std;int mi[16] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};struct Course{char name[100];int deadline;int duration;};struct Status{	int usedDays;	int delayDays;	int pre;	int mask;	Status()	{		mask=0;		delayDays=-1;	}};struct in{	int nums[7000];	int count;};Course courses[16];Status dp[33000][16];int main(){    int test=0,n;    cin>>test;    while(test>0)    {        cin>>n;        for(int i=1;i<=n;i++)            cin>>courses[i].name>>courses[i].deadline>>courses[i].duration;		for(int i=0;i<33000;i++)			for(int j=0;j<16;j++)			{				dp[i][j].mask=0;				dp[i][j].delayDays=8000;			}		in ins[16];		for(int i=1;i<=15;i++)			ins[i].count=0;		for(int i=1;i<=n;i++)		{			dp[mi[n-i]][1].usedDays=courses[i].duration;			dp[mi[n-i]][1].delayDays= (courses[i].duration >  courses[i].deadline )? (courses[i].duration -  courses[i].deadline):0;			dp[mi[n-i]][1].pre=0;			dp[mi[n-i]][1].mask=mi[n-i];			ins[1].count++;			ins[1].nums[ins[1].count]=mi[n-i];		}		for(int i=2;i<=n;i++)		{			int value;			for(int j=1;j<=ins[i-1].count;j++)			{				value = ins[i-1].nums[j];				for(int k=n;k>=1;k--)				{					if((value&mi[k-1])==0)					{						int usedDays =courses[n-k+1].duration + dp[value][i-1].usedDays;						int min = usedDays > courses[n-k+1].deadline ? (usedDays - courses[n-k+1].deadline):0;						min+=dp[value][i-1].delayDays;						if(dp[value+mi[k-1]][i].delayDays==8000)						{								ins[i].count++;								ins[i].nums[ins[i].count]=value+mi[k-1];						}						if(dp[value+mi[k-1]][i].delayDays==8000 || dp[value+mi[k-1]][i].delayDays>min)						{							dp[value+mi[k-1]][i].delayDays = min;							dp[value+mi[k-1]][i].pre = value;							dp[value+mi[k-1]][i].usedDays =usedDays;						}						dp[value+mi[k-1]][i].mask = value+mi[k-1];					}				}			}		}		cout<
       
        <
        
         =0)		{			sts[k]=re.mask;			if(k>0)				re=dp[re.pre][k-1];			k--;		}		k=0;		int t_mask;		while(k<=n)		{			if(k==0)				t_mask=sts[k];			else			{				int t = (t_mask^sts[k]);				for(int p=0;p<=15;p++)				{					if(mi[p]==t)					{						cout<
         
          <