题意：有n门功课需要完成，每一门功课都有时间期限以及你完成所需要的时间，如果完成的时间超出时间期限多少单位，就会被减多少学分，问以怎样的功课完成顺序，会使减掉的学分最少，有多个解时，输出功课名字典序最小的一个。
作业最多只有15个，容易想到是状态压缩 dp[i]表示i对应状态的最小扣分 i转换为二进制后为1的位表明该位对应的作业已经做了，为0的位没做。
dp[i] = min{dp[k] + cost | k为将某一位变成1后等于 i 的状态}
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 16; 9 struct Node 10 { 11 char str[109]; 12 int want, need; 13 }node[N]; 14 15 struct DP // 状态 16 { 17 int now, sum, pre, pos; // 当前状态的时间，总惩罚，前一个选择，当前选择 18 }dp[1<<N]; 19 20 void put_ans(int x) 21 { 22 if(dp[x].pre != -1) 23 { 24 put_ans(dp[x].pre); 25 printf("%s\n", node[dp[x].pos].str); 26 } 27 } 28 29 int main () { 30 31 int T; 32 scanf("%d",&T); 33 while(T--) 34 { 35 int n; 36 scanf("%d",&n); 37 for(int i=0;i<n;i++) 38 scanf("%s%d%d", node[i].str, &node[i].want, &node[i].need); 39 dp[0].now = dp[0].sum = 0; 40 dp[0].pre = dp[0].pos = -1; 41 int m = (1<<n)-1; 42 for(int i=1; i<=m; i++) 43 { 44 dp[i].sum=0x3f3f3f3f; 45 for(int j=0; j<n; j++) 46 { 47 if((1<<j) & i) 48 { 49 int k = i - (1<<j); 50 int v = dp[k].now + node[j].need - node[j].want; 51 v = max(v, 0); 52 if(dp[i].sum >= dp[k].sum+v)//必须有等号，这样保持字典序 53 { 54 dp[i].sum = dp[k].sum + v; 55 dp[i].now = dp[k].now + node[j].need; 56 dp[i].pre = k; 57 dp[i].pos = j; 58 } 59 } 60 } 61 } 62 printf("%d\n", dp[m].sum); 63 put_ans(m); 64 } 65 return 0; 66 }