题目链接：
题目描述：
有n种甜点，每种都有三个属性（能量，空间，数目），有m辆卡车，每种都有是三个属性（空间，花费，数目）。问至少运输p能量的甜点，花费最小是多少？
解题思路：
明显可以看出是多重背包搞两次，但是数据范围太大了，背包要到2*1e6，感觉会TLe。还是呆呆的写了一发，果断超啊！然后滚回去看背包九讲课件了，看到了二进制压缩的时候，感觉可以搞这个题目。试了一下果然AC，原本物品数目是100*100，二进制压缩以后也就是100*log2100个左右，然后进行01背包就OK咯！
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int INF = 0x3f3f3f3f; 7 const int maxn = 55000; 8 const int N = 2000; 9 int dp[maxn], x, y, c1, c2; 10 int dcos[N], dval[N], tcos[N], tval[N]; 11 void display () 12 { 13 for (int i=0; i<c1+200; i++) 14 dp[i] = INF; 15 dp[0] = 0; 16 for (int i=0; i<x; i++) 17 for (int j=c1+200; j>=dval[i]; j--) 18 dp[j] = min (dp[j], dp[j-dval[i]]+dcos[i]); 19 c2 = dp[c1]; 20 for (int i=c1; i<c1+200; i++) 21 c2 = min (dp[i], c2); 22 } 23 void solve () 24 { 25 memset (dp, 0, sizeof(dp)); 26 for (int i=0; i<y; i++) 27 for (int j=50000; j>=tcos[i]; j--) 28 dp[j] = max (dp[j], dp[j-tcos[i]]+tval[i]); 29 for (int i=1; i<=50000; i++) 30 if (dp[i] >= c2) 31 { 32 printf ("%d ", i); 33 return ; 34 } 35 printf ("TAT "); 36 } 37 int main () 38 { 39 int t, n, m; 40 scanf ("%d", &t); 41 while (t --) 42 { 43 scanf ("%d %d %d", &n, &m, &c1); 44 int a, b, c; 45 x = y = 0; 46 for (int i=0; i<n; i++) 47 { 48 scanf ("%d %d %d", &a, &b, &c); 49 for (int k=1; c; k*=2) 50 { 51 int num = min (k, c); 52 dcos[x] = num * b; 53 dval[x++] = num * a; 54 c -= num; 55 } 56 } 57 for (int i=0; i<m; i++) 58 { 59 scanf ("%d %d %d", &a, &b, &c); 60 for (int k=1; c; k*=2) 61 { 62 int num = min (k, c); 63 tcos[y] = num * b; 64 tval[y++] = num * a; 65 c -= num; 66 } 67 } 68 display (); 69 solve (); 70 } 71 return 0; 72 }