DP专题·三(01背包+完全背包)-白红宇

DP专题·三(01背包+完全背包)

阅读量：6546 次

发布时间：2019-06-24

本文共 18542 字，大约阅读时间需要 61 分钟。

1、hdu 2126 Buy the souvenirs

　　题意：给出若干个纪念品的价格，求在能购买的纪念品的数目最大的情况下的购买方案。

　　思路：01背包+记录方案。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn = 35; 6 const int maxw = 510; 7 int cnt[maxw]; 8 int dp[maxw]; 9 int p[maxn];10 int main()11 {12     int t;13     scanf("%d", &t);14     while (t--)15     {16         int n, m;17         scanf("%d%d", &n, &m);18         for (int i = 0; i < n; i++) scanf("%d", p + i);19         memset(dp, 0, sizeof(dp));20         memset(cnt, 0, sizeof(cnt));21         for (int i = 0; i < n; i++)22         {23             for (int v = m; v >= p[i]; v--)24             {25                 if (dp[v - p[i]]+1 > dp[v])26                 {27                     dp[v] = dp[v - p[i]]+1;28                     cnt[v]=cnt[v-p[i]]==0?1:cnt[v-p[i]];29                 }30                 else if (dp[v - p[i]] + 1 == dp[v])31                 {32                     cnt[v] += cnt[v - p[i]]==0?1:cnt[v-p[i]];33                 }34             }35         }36         if (dp[m] != 0)printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", cnt[m], dp[m]);37         else printf("Sorry, you can't buy anything.\n");38     }39     return 0;40 }

View Code

2、hdu 4281 Judges' response(状态压缩+01背包+MTSP问题)

　　题意：有n-1个参赛者，给出裁判和n-1个人的位置坐标、裁判和n-1个人的提问时间（裁判为0）。裁判有最长回答时间。

　　　　问：

　　　　　　①最少需要多少个裁判？

　　　　　　②当裁判数目无穷多时，问从初始点出发去解答参赛者提问后回到初始点的走过的最少距离。

　　思路：第一问可以用状态压缩+01背包解决；第二问MTSP问题

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6   7 using namespace std;  8 const int maxn = 16;  9 const int maxm = 100010; 10 const int INF = 0x3f3f3f3f; 11 int n, m,maxtot; 12 int mp[maxn][maxn];//记录两两之间距离 13 int st[1 << maxn];//记录可行状态 14 bool ok[1 << maxn];//标记可行状态 15 int dp[1 << maxn];//记录当前状态下所需最少的裁判 16 int x[maxn],y[maxn];//记录坐标 17 int w[maxn];//记录提问时间 18 int tdis[maxn][1 << maxn];//tdis[i][j]表示在j状态下最后停在i处时的最小花费 19 int mdis[1 << maxn];//表示i这种状态下回到起点的最小花费 20  21  22 bool check(int cst) 23 { 24     int sum = 0; 25     for (int i = 0; i < n; i++) 26     { 27         if (cst&(1 << i)) sum += w[i]; 28     } 29     return sum <= m; 30 } 31  32 void Init() 33 { 34     for (int i = 0; i < n; i++) 35     { 36         for (int j = 0; j < n; j++) 37         { 38             mp[i][j] = ceil(sqrt(1.0*(x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]))); 39         } 40     } 41     memset(tdis, INF, sizeof(tdis)); 42     memset(mdis, INF, sizeof(mdis)); 43     tdis[0][1] = 0;//从起点到起点距离为0 44 } 45  46 int MTSP() 47 { 48     //得到每一条可行路径的最优解 49     for (int i = 1; i <= maxtot; i++) 50     { 51         if (ok[i]) 52         { 53             for (int j = 0; j < n; j++) 54             { 55                 if (i&(1 << j)) 56                 { 57                     mdis[i] = min(mdis[i], tdis[j][i]+mp[j][0]);//i这种状态最后回到原点0的最小值={min(tdis[j][i]+mp[j][0])|0<=j
           
            << n) - 1; 91 int tot = 0; 92 memset(ok, 0, sizeof(ok)); 93 for (int i = 1; i <= maxtot; i++) 94 { 95 if (check(i)) 96 { 97 ok[i] = true; 98 st[tot++] = i; 99 }100 }101 //dp求解最小裁判数目102 memset(dp, INF, sizeof(dp));103 dp[0] = 0;104 for (int i = 0; i < tot; i++)105 {106 for (int j = maxtot; j >= 0; j--)107 {108 if (dp[j] != INF && (j&st[i]) == 0)109 {110 dp[st[i] | j] = min(dp[j] + 1, dp[st[i] | j]);111 }112 }113 }114 int ans1 = 0, ans2 = 0;115 if (dp[maxtot] == INF)116 {117 ans1 = ans2 = -1;118 }119 else120 {121 ans1 = dp[maxtot];122 //求解多旅行商（MTSP）问题123 Init();124 ans2 = MTSP();125 }126 printf("%d %d\n", ans1, ans2);127 }128 return 0;129 }

View Code

3、uva 674 Coin Change

　　题意：有5中面值的硬币，需要凑成n元，有多少种方案。

　　思路：完全背包+记录方案数

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int maxn = 8000; 5 int dp[maxn]; 6 int cnt[maxn]; 7 int v[] = {
    1, 5, 10, 25, 50}; 8 int main() 9 {10     int n;11     while (~scanf("%d", &n))12     {13         memset(dp, 0, sizeof(dp));14         memset(cnt, 0, sizeof(cnt));15         cnt[0] = 1;16         for (int i = 0; i < 5; i++)17         {18             for (int tv = v[i]; tv <= n; tv++)19             {20                 if (dp[tv] == dp[tv - v[i]] + v[i]) cnt[tv] += cnt[tv - v[i]];21                 else if (dp[tv] < dp[tv - v[i]] + v[i])22                 {23                     dp[tv] = dp[tv - v[i]] + v[i];24                     cnt[tv] = cnt[tv - v[i]];25                 }26             }27         }28         printf("%d\n", cnt[n]);29     }30     return 0;31 }

View Code

4、uva 147 Dollars

　　题意：有11中面值，求凑成n元的方案数

　　思路：先把n转换成整数，然后完全背包

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int maxn = 30010; 5 int dp[maxn]; 6 long long cnt[maxn];//爆int 7 int v[] = { 10000,5000,2000,1000,500,200,100,50,20,10,5 }; 8 //另一种方法：用dp[i][j]表示用前i种硬币，组成j分的种类数， 9 //状态转移方程：dp[i][j] += DP(i - 1, j - k*d[i])10 int main()11 {12     double n;13     while (~scanf("%lf", &n))14     {15         int N = int(n * 100+0.5);//精度问题16         if (N == 0)break;17         memset(dp, 0, sizeof(dp));18         memset(cnt, 0, sizeof(cnt));19         cnt[0] = 1;20         for (int i = 0; i < 11; i++)21         {22             for (int tv = v[i]; tv <= N; tv++)23             {24                 if (dp[tv] == dp[tv - v[i]] + v[i]) cnt[tv] += cnt[tv - v[i]];25                 else if (dp[tv] < dp[tv - v[i]] + v[i])26                 {27                     dp[tv] = dp[tv - v[i]] + v[i];28                     cnt[tv] = cnt[tv - v[i]];29                 }30             }31         }32         printf("%6.2lf%17lld\n",n, cnt[N]);33     }34     return 0;35 }

View Code

5、poj 3181 Dollar Dayz

　　题意：有1~k中面值，凑成n元的方案数。

　　思路：会爆long long,用大数+完全背包。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn = 1010; 6 int dp[maxn]; 7 long long cnt1[maxn],cnt2[maxn]; 8 const long long MAX = 1e18; 9 int main()10 {11     int n,k;12     while (~scanf("%d%d", &n,&k))13     {14         memset(dp, 0, sizeof(dp));15         memset(cnt1, 0, sizeof(cnt2));16         memset(cnt2, 0, sizeof(cnt2));17 18         cnt1[0] = 1;19         for (int i = 1; i <=k; i++)20         {21             for (int tv = i; tv <= n; tv++)22             {23                 if (dp[tv] == dp[tv - i] + i)24                 {25                     cnt2[tv] +=cnt2[tv-i]+(cnt1[tv]+cnt1[tv - i])/MAX;26                     cnt1[tv] = (cnt1[tv] + cnt1[tv - i]) % MAX;27                 }28                 else if (dp[tv] < dp[tv -i] + i)29                 {30                     dp[tv] = dp[tv - i] + i;31                     cnt1[tv] = cnt1[tv - i];32                     cnt2[tv] = cnt2[tv - i];33                 }34             }35         }36         if (cnt2[n])printf("%lld%lld\n", cnt2[n], cnt1[n]);37         else printf("%lld\n", cnt1[n]);38     }39     return 0;40 }

View Code

6、poj 3260 The Fewest Coins

　　题意：有n种面值的硬币，一位农夫带着每种硬币各ci个去买价值为T的商品，售货员可以找零任意多个硬币。问，农夫交给售货员的硬币和售货员找回的硬币之和最小为多少？

　　思路：对农夫多重背包(二进制优化)，对售货员完全背包，找当前价格tv下的最小硬币数目。确定上限：前者为T+max(vi)*max(vi);后者为max(vi)*max(vi)。（鸽巢原理）（假设存在一种最优支付方案，给了多于t + max_v * max_v的钱，那么商店就会找回多于max_v * max_v的钱，这些硬币的个数大于max_v。设这些硬币的面值分别为a_i，根据鸽笼原理的应用，硬币序列中存在至少两个子序列，这两个子序列的和分别都能被max_v整除。如果我们直接用长度更小的那个子序列换算为面值为max_v的硬币某整数个，再去替换母序列就能用更少的硬币买到商品，形成矛盾。）

鸽巢原理（抽屉原理或狄利克雷原理）的应用：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7  8 const int maxv1 = 10000 + 120 * 120 + 10; 9 const int maxv2 = 120 * 120 + 10;10 const int maxn = 110;11 const int INF = 0x3f3f3f3f;12 int val[maxn];13 int num[maxn];14 int n, t;15 int dp1[maxv1];16 int dp2[maxv2];17 int main()18 {19     while (~scanf("%d%d", &n, &t))20     {21         int maxv = 0;22         for (int i = 0; i < n; i++) scanf("%d", val + i),maxv=max(maxv,val[i]);23         for (int i = 0; i < n; i++) scanf("%d", num + i);24         //农夫多重背包，找tv下最小硬币数25         int maxsum = t + maxv*maxv;26         memset(dp1, INF, sizeof(dp1));27         dp1[0] = 0;28         for (int i = 0; i < n; i++)29         {30             int k = 1;31             bool flag = true;32             while (flag)33             {34                 if (k>num[i])35                 {36                     k = num[i] - k / 2;37                     flag = false;38                 }39                 for (int tv = maxsum; tv >= k*val[i]; tv--)40                 {41                     dp1[tv] = min(dp1[tv], dp1[tv - k*val[i]] + k);42                 }43                 k *= 2;44             }45         }46         //销售员完全背包，找tv下最少硬币数47         int maxsum2 = maxv*maxv;48         memset(dp2, INF, sizeof(dp2));49         dp2[0] = 0;50         for (int i = 0; i < n; i++)51         {52             for (int j = val[i]; j <= maxsum2; j++)53             {54                 dp2[j] = min(dp2[j], dp2[j - val[i]] + 1);55             }56         }57 58         int ans = INF;59         for (int i = t; i <= maxsum; i++) ans = min(ans, dp1[i] + dp2[i - t]);60         if(ans!=INF)printf("%d\n", ans);61         else printf("-1\n");62     }63     return 0;64 }

View Code

7、poj 2063 Investment

　　题意：有若干基金可以选择，初始有一定的资金，问过一定年数后最大的本息？

　　思路：对每一年用完全背包求当前本金下所能获得的最多利润，累加本息。由于题目保证本金和基金的价格都是1000的倍数，dp时可以/1000.

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7  8 const int maxv = 50100; 9 const int maxn = 15;10 int val[maxn];11 int itst[maxn];12 int dp[maxv];13 14 int main()15 {16     int t;17     scanf("%d", &t);18     while (t--)19     {20         int st, year;21         scanf("%d%d", &st, &year);22         int n;23         scanf("%d", &n);24         for (int i = 0; i < n; i++) scanf("%d%d", val + i, itst + i),val[i]/=1000;25         int ans = st;26         memset(dp, 0, sizeof(dp));27         for (int i = 0; i < year; i++)28         {29             int tot = ans / 1000;30             for (int j = 0; j < n; j++)31             {32                 for (int tv = val[j]; tv <= tot; tv++)33                 {34                     dp[tv] = max(dp[tv], dp[tv - val[j]] + itst[j]);35                 }36             }37             ans += dp[tot];38         }39         printf("%d\n", ans);40     }41     return 0;42 }

View Code

8、zoj 3623 Battle Ships

　　题意：有一个塔楼，有L点血。有n种船，每时刻在建造的船最多只有一艘。问最少的时间。

　　思路：dp[i]表示前i秒所能造成的最大伤害。dp[i+cost[j]]=max(dp[i+cost[j]],dp[i]+i*dps[j]).可以这么理解，在第i+1到i+cost[j]内建造船j,有i秒可以让其输出。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6  7 const int maxt = 350; 8 const int maxn = 35; 9 int dp[maxt];//dp[i]表示前i秒能造成的最大伤害10 int dps[maxn];11 int cost[maxn];12 13 int main()14 {15     int n, l;16     while (~scanf("%d%d", &n, &l))17     {18         for (int i = 0; i < n; i++) scanf("%d%d", cost + i, dps + i);19         memset(dp, 0, sizeof(dp));20         int ans = maxt;21         for (int i = 0; i < n; i++)22         {23             for (int j =0; j < maxt-cost[i]; j++)24             {25                 dp[j + cost[i]] = max(dp[j + cost[i]], dp[j] + j*dps[i]);26                 if (dp[j + cost[i]] >= l) ans = min(ans, j + cost[i]);27             }28         }29         printf("%d\n", ans);30     }31     return 0;32 }

View Code

9、zoj 3524 Crazy Shopping

　　题意：有一个有向无环图，图上有n个点，每个地点有一种占用V空间，价值为W的物品，现在一个人从某点出发，如果背包有C重量的物品，走过路程为K，会消耗C*K的体力，那么在背包容量一定的情况下，我要得到最大的价值需要消耗的最少体力是多少。

　　思路：拓扑排序+完全背包+记录耗能

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 9 int N, M, W,X;//景点数目、道路条数、背包容量、起始点 10 const int maxn = 610; 11 const int maxm = 60010; 12 const int maxw = 2010; 13 14 long long dp[maxn][maxw],mcost[maxn][maxw];//[i][j],表示走到i时，背包装有质量为j的最大价值及其最小耗能 15 16 struct node 17 { 18 int to, len; 19 node(int tt=0,int ll=0):to(tt),len(ll){ } 20 }; 21 vector
            
             mp[maxn]; 22 23 int tw[maxn], tv[maxn];//重量及其价值 24 25 int TPOrder[maxn];//记录拓扑排序 26 bool ok[maxn];//表示能否从起点X到达该点 27 int indgree[maxn];//记录入度 28 29 void Init() 30 { 31 X--; 32 for (int i = 0; i <= N; i++) mp[i].clear(); 33 memset(ok, 0, sizeof(ok)); 34 memset(dp, 0, sizeof(dp)); 35 memset(mcost, -1, sizeof(mcost)); 36 memset(indgree, 0, sizeof(indgree)); 37 } 38 39 void GetWV() 40 { 41 for (int i = 0; i < N; i++) scanf("%d%d", tw + i, tv + i); 42 } 43 44 void GetMP() 45 { 46 for (int i = 0; i < M; i++) 47 { 48 int from, to, len; 49 scanf("%d%d%d", &from, &to, &len); 50 from--, to--; 51 mp[from].push_back(node(to, len));//有向边 52 indgree[to]++; 53 } 54 } 55 56 void GetTP() 57 { 58 queue
             
              q; 59 int index = 0; 60 for (int i = 0; i < N; i++) if (indgree[i] == 0) q.push(i); 61 while (!q.empty()) 62 { 63 int u = q.front(); 64 q.pop(); 65 TPOrder[index++] = u; 66 int sz = mp[u].size(); 67 for (int i = 0; i < sz; i++) 68 { 69 int v = mp[u][i].to; 70 if (indgree[v]) 71 { 72 indgree[v]--; 73 if (indgree[v] == 0) q.push(v); 74 } 75 } 76 } 77 } 78 79 long long Solve() 80 { 81 long long maxv = 0, mindis = 0; 82 for (int i = 0; i <= W; i++) mcost[X][i] = 0; 83 for (int w = tw[X]; w <= W; w++) 84 { 85 dp[X][w] = max(dp[X][w], dp[X][w - tw[X]] + tv[X]); 86 if (dp[X][w] > maxv) maxv = dp[X][w], mindis = 0; 87 } 88 ok[X] = true; 89 for (int j = 0; j < N; j++) 90 { 91 int u = TPOrder[j]; 92 if (!ok[u])continue; 93 int sz = mp[u].size(); 94 for (int k = 0; k < sz; k++) 95 { 96 int v = mp[u][k].to, len = mp[u][k].len; 97 ok[v] = true; 98 //先到达 99 for (int i = 0; i <= W; i++)100 {101 if (dp[v][i] < dp[u][i])102 {103 dp[v][i] = dp[u][i];104 mcost[v][i] = mcost[u][i] + len*i;105 }106 else if (dp[v][i] == dp[u][i])107 {108 if (mcost[v][i] == -1) mcost[v][i] = mcost[u][i] + len*i;109 else mcost[v][i] = min(mcost[v][i], mcost[u][i] + len*i);110 }111 if (i>0&&dp[v][i] == dp[v][i - 1]) mcost[v][i] = min(mcost[v][i], mcost[v][i - 1]);112 }113 //再购买114 for (int i = tw[v]; i <= W; i++)115 {116 if (dp[v][i] < dp[v][i - tw[v]] + tv[v])117 {118 dp[v][i] = dp[v][i - tw[v]] + tv[v];119 mcost[v][i] = mcost[v][i - tw[v]];120 }121 else if (dp[v][i] == dp[v][i - tw[v]] + tv[v]) mcost[v][i] = min(mcost[v][i], mcost[v][i - tw[v]]);122 }123 //更新ans124 for (int i = 0; i <= W; i++)125 {126 if (dp[v][i] > maxv) maxv = dp[v][i], mindis = mcost[v][i];127 else if (dp[v][i] == maxv) mindis = min(mindis, mcost[v][i]);128 }129 }130 }131 return mindis;132 }133 134 int main()135 {136 while (~scanf("%d%d%d%d", &N, &M, &W, &X))137 {138 Init();139 GetWV();140 GetMP();141 GetTP();//拓扑排序142 long long ans=Solve();143 printf("%lld\n", ans);144 }145 return 0;146 }

View Code

10、zoj 3662 Math Magic

　　题意：定义k个数和为N，k个数的最小公倍数为M，求k个数的方案？

　　思路：滚动数组dp[now][j][k]表示选当前个数的数，和为j，最小公倍数为k的方案数，dp[now][sv + val][LCM[tlcm][ind]] = dp[now][sv + val][LCM[tlcm][ind]] + dp[now ^ 1][sv][tlcm]。所选择的数必须是M的因子。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int N, M, K; 7 const int maxn = 1010; 8 const int maxm = 1010; 9 const int maxk = 110;10 const int maxfac = 40;11 const int MOD = 1e9 + 7;12 int factor[maxm];13 int pos[maxm];14 int LCM[maxm][maxm];15 16 int dp[2][maxn][maxfac];//滚动数组dp[now][j][k]表示选当前个数的数，和为j，最小公倍数为k的方案数17 18 int Gcd(int a, int b)19 {20     if (a < b) a = a^b, b = a^b, a = a^b;21     while (a%b)22     {23         int t = a % b;24         a = b;25         b = t;26     }27     return b;28 }29 int Lcm(int a, int b)30 {31     return a*b / Gcd(a, b);32 }33 int main()34 {35     while (~scanf("%d%d%d", &N, &M, &K))36     {37         int cnt = 0;38         //找到所有因子(1000以内因子最多只有32个)39         for (int i = 1; i <= M; i++)40         {41             if (M%i == 0) factor[++cnt] = i,pos[i]=cnt;42         }43         //得到所有因子两两的最小公倍数(该最小公倍数一定是其他某个因子)44         memset(LCM, 0, sizeof(LCM));45         for (int i = 1; i <= cnt; i++)46         {47             for (int j = i; j <= cnt; j++)48             {49                 int lcm = Lcm(factor[i], factor[j]);50                 LCM[i][j] = LCM[j][i] = pos[lcm];51             }52         }53         //dp-完全背包54         memset(dp, 0, sizeof(dp));55         int now = 0;56         for (int i = 1; i <= cnt; i++) dp[now][factor[i]][i] = 1;57         for (int t = 2; t <= K; t++)58         {
    //选第t个数59             now ^= 1;60             memset(dp[now], 0, sizeof(dp[now]));//注意清零61             for (int sv = t - 1; sv <= N; sv++)62             {
    //和为sv63                 for (int tlcm = 1; tlcm <= cnt; tlcm++)64                 {
    //前一层的LCM65                     if (dp[now ^ 1][sv][tlcm] == 0) continue;66                     for (int ind = 1; ind <= cnt; ind++)67                     {
    //枚举所加的数68                         69                         int val = factor[ind];70                         if (sv + val > N)continue;71                         dp[now][sv + val][LCM[tlcm][ind]] = (dp[now][sv + val][LCM[tlcm][ind]] + dp[now ^ 1][sv][tlcm]) % MOD;72                     }73                 }74             }75         }76         printf("%d\n", dp[now][N][cnt]);77     }78     return 0;79 }

View Code

11、zoj 3956 Course Selection System

　　题意：有n门课程，每门课有Hi、Ci值。现在需要选若干门课程，使得SumH^2-SumH*SumC-SumC^2值最大。

　　思路：01背包，把C看成体积，H看成价值。当C固定时，求出最大的SumH.最后遍历dp数组得到最大值（如果一个i值不能有Ci值组成，其SumH肯定和小于i的某一个值相同，而那个值的算式结果肯定比其大）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int MAXC = 50010; 7 long long dp[MAXC]; 8 const long long INF = 0x3f3f3f3f3f3f3f3f; 9 const int maxn = 510;10 int h[maxn], c[maxn];11 int main()12 {13     int t;14     scanf("%d", &t);15     while (t--)16     {17         int n;18         scanf("%d", &n);19         int sumc = 0;20         for (int i = 0; i < n; i++) scanf("%d%d", h + i, c + i),sumc+=c[i];21         memset(dp, 0, sizeof(dp));22         long long ans = 0;23         for (int i = 0; i < n; i++)24         {25             for (int j = sumc; j >= c[i]; j--)26             {27                 dp[j] = max(dp[j], dp[j - c[i]] + h[i]);28             }29         }30         for (int i = 0; i <= sumc; i++) ans = max(ans, 1ll*dp[i] * dp[i] - dp[i] * i - i * i);31         printf("%lld\n", ans);32     }33     return 0;34 }