• 算法竞赛备赛进阶之背包问题训练

    目录

    1.滑动窗口

    2.多重背包问题 III

    3.采药

    4.装箱问题

    5.宠物小精灵之收服

    6.二维费用的背包问题

    7.潜水员

    8.数字组合

    9.庆功宴

    10.买书

    11.背包问题求具体方案

    12.分组背包问题

    13.机器分配

    14.金明的预算方案

    15.开心的金明

    16.货币系统

    17.货币系统2

    18.混合背包问题

    19.有依赖的背包问题

    20.背包问题求方案数

    21.能量石

    背包问题闫氏分析法回顾：

    1. 状态表示f[i, j]

      1. 集合：所有只从当前i个物品中选，且总体积不超过j的选法的集合

      2. 属性：Max/Min/X+Count

    2. 状态计算：按最后一步来划分

    01背包问题：每个物品选与不选

    完全背包问题：每个物品选0，选1个，选2个，.....

    多重背包问题：每个物品选0，.........,选si个

    总结：只有完全背包问题，当空间优化成一维以后，背包问题的体积是从小到大循环的；而其它的背包问题都是从大到小循环的。

    1.滑动窗口

    给定一个大小为 n≤106 的数组。

    有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

    你只能在窗口中看到 k 个数字。

    每次滑动窗口向右移动一个位置。

    以下是一个例子：

    该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

    窗口位置最小值最大值
    [1 3 -1] -3 5 3 6 7-13
    1 [3 -1 -3] 5 3 6 7-33
    1 3 [-1 -3 5] 3 6 7-35
    1 3 -1 [-3 5 3] 6 7-35
    1 3 -1 -3 [5 3 6] 736
    1 3 -1 -3 5 [3 6 7]37

    你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

    多重背包：求滑动窗口内的最大值。

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 1000010;
    7. ​
    8. int n;
    9. int a[N], q[N];
    10. ​
    11. int main()
    12. {
    13.     scanf("%d", &n);
    14.     for(int i = 0;i < n; i++) scabf("%d", &a[i]);
    15.     
    16.     int hh = 0, tt = -1;
    17.     for(int i = 0;
    18.     return 0;
    19. }

    2.多重背包问题 III

    有 N 种物品和一个容量是 V 的背包。

    第 ii 种物品最多有 si 件，每件体积是 vi，价值是 wi。

    求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

    多重背包队列优化

    1. #include
    2. #include
    3. #include
    4. #include
    5. ​
    6. using namespace std;
    7. ​
    8. const int N = 20010;
    9. ​
    10. int n, m;
    11. int f[N], g[N], q[N];
    12. ​
    13. int main()
    14. {
    15.     scanf("%d%d", &n, &m);
    16.     for(int i = 0;i < n; i++)
    17.     {
    18.         int v, w, s;
    19.         cin >> v >> w >> s;
    20.         memcpy(g, f, sizeof(f));
    21.         for(int j = 0;j < v; j++)
    22.         {
    23.             int hh = 0, tt = -1;
    24.             for(int k = j;k <= m; k += v)
    25.             {
    26.                 f[k] = g[k];
    27.                 if(hh <= tt && q[hh] < k - s * v) hh++;
    28.                 if(hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
    29.                 while(hh <= tt && g[q[tt]] + (j - q[tt]) / v * w <= g[k] - (k - j) / v * w) tt--;
    30.                 q[ ++tt ] = k;
    31.             }
    32.         }
    33.     }
    34.     
    35.     cout << f[m] << endl;
    36.     
    37.     return 0;
    38. }

    3.采药

    辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。

    为此，他想拜附近最有威望的医师为师。

    医师为了判断他的资质，给他出了一个难题。

    医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 1010;
    6. ​
    7. int n, m;
    8. int f[N];
    9. ​
    10. int main()
    11. {
    12.     cin >> n >> m;
    13.     for(int i = 0;i < m; i++)
    14.     {
    15.         int v, w;
    16.         cin >> v >> w;
    17.         for(int j = n;j >= v; j--) f[j] = max(f[j], f[j - v] + w);
    18.     }
    19.     
    20.     cout << f[n] << endl;
    21.     
    22.     return 0;
    23. }

    4.装箱问题

    输入格式为第一行一个整数V，表示箱子容量。第二行一个整数n，表示物品数。接下来n行，每行一个正整数（不超过10000），分别表示这n个物品的各自体积。输出格式为一个整数，表示箱子剩余空间。剩余空间要最小。

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 10010;
    6. ​
    7. int n;
    8. int V;
    9. int f[N];
    10. ​
    11. int main()
    12. {
    13.     cin >> V >> n;
    14.     
    15.     for(int i = 0;i < n; i++)
    16.     {
    17.         int v;
    18.         cin >> v;
    19.         for(int j = V;j >= v; j--) f[j] = max(f[j], f[j - v] + v);
    20.     }
    21.     
    22.     cout << V - f[V] << endl;
    23.     
    24.     return 0;
    25. }

    5.宠物小精灵之收服

    宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

    一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时，狩猎也宣告结束。

    我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

    小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

    现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

    花费1：精灵球数量

    花费2：皮卡丘体力值

    价值：小精灵的数量

    状态表示：f[i,j,k]表示所有只从前i个物品中选，且花费1不差于j，花费2不超过k的选项的最大价值

    状态计算：f[i,j,k] = max(f[i-1,j,k], f[i-1,j-v1[i],k-v2[i]]+ 1)

    最多收服的小精灵个数：f[K, N, M]

    最少消耗的体力怎么计算：f[K,N,m] == f[K,N,M]

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 1010, M = 510;
    6. ​
    7. int n, V1, V2;
    8. int f[N][N];
    9. ​
    10. int main()
    11. {
    12.     cin >> V1 >> V2 >> n;
    13.     for(int i = 0;i < n; i++)
    14.     {
    15.         int v1, v2;
    16.         cin >> v1 >> v2;
    17.         for(int j = V1;j >= v1; j--)
    18.             for(int k = V2 - 1;k >= v2; k--)
    19.                 f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    20.     }
    21.     
    22.     cout << f[V1][V2 - 1] << ' ';
    23.     int k = V2 - 1;
    24.     while(k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k--;
    25.     cout << V2 - k << endl;
    26.     
    27.     return 0;
    28. }

    6.二维费用的背包问题

    有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

    每件物品只能用一次。体积是 vi，重量是 mimi，价值是 wi。

    求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。 输出最大价值。

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 110;
    6. ​
    7. int n, V, M;
    8. int f[N][N];
    9. ​
    10. int main()
    11. {
    12.     cin >> n >> V >> M;
    13.     
    14.     for(int i = 0;i < n; i++)
    15.     {
    16.         int v, m, w;
    17.         cin >> v >> m >> w;
    18.         for(int j = V;j >= v; j--)
    19.             for(int k = M;k >= m; k--)
    20.                 f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    21.     }
    22.     
    23.     cout << f[V][M] << endl;
    24.     
    25.     return 0;
    26. }

    7.潜水员

    潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？

    注意：当j-v1和k-v2为负数的话，全部都变成0，需要转移，不然会出错。

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 22, M = 80;
    7. ​
    8. int n, m, k;
    9. int f[N][M];
    10. ​
    11. int main()
    12. {
    13.     cin >> n >> m >> k;
    14.     
    15.     memset(f, -1, sizeof(f));
    16.     f[0][0] = 0;
    17.     
    18.     for(k--)
    19.     {
    20.         int v1, v2, w;
    21.         cin >> v1 >> v2 >> w;
    22.         for(int i = n;i >= v1; i--)
    23.             for(int j = m;j >= 0; j--)
    24.                 f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
    25.     }
    26.     
    27.     cout << f[n][m] << endl;
    28.     
    29.     return 0;
    30. }

    8.数字组合

    给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 10010;
    6. ​
    7. int n, m;
    8. int f[N];
    9. ​
    10. int main()
    11. {
    12.     cin >> n >> m;
    13.     f[0] = 1;
    14.     for(int i = 0;i < n; i++)
    15.     {
    16.         int v;
    17.         cin >> v;
    18.         for(int j = m;j >= v; j--)
    19.             f[j] += f[j - v];
    20.     }
    21.     
    22.     cout << f[m] << endl;
    23.     return 0;
    24. }

    9.庆功宴

    为了庆祝班级在校运动会上取得全校第一名成绩，班主任决开一经庆功会，为此表欢购买奖品犒劳运动员。期望拨款能购买最大价值的奖品，以补充他们的精力和体力。

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 6010;
    6. ​
    7. int n, m;
    8. int f[N];
    9. ​
    10. int main()
    11. {
    12.     cin >> n >> m;
    13.     
    14.     for(int i = 0;i < n; i++)
    15.     {
    16.         int v, w, s;
    17.         cin >> v >> w >> s;
    18.         for(int j = m;j >= 0; j--)
    19.             for(int k = 0;k <= s && k * s <= j; k++)
    20.                 f[j] = max(f[j], f[j - k * v] + w);
    21.     }
    22.     
    23.     cout << f[m] << endl;
    24.     
    25.     return 0;
    26. }

    10.买书

    小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。问小明有多少种买书方案？（每种书可购买多本）

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 1010;
    6. ​
    7. int v[5] = {0, 10, 20, 50, 100};
    8. int f[4][N];
    9. ​
    10. int main()
    11. {
    12.     int m;
    13.     cin >> m;
    14.     
    15.     f[0][0] = 1;
    16.     
    17.     for(int i = 1;i <= n; i++)
    18.         for(int j = 0;j <= m; j++)
    19.         {
    20.             f[i][j] = f[i - 1][j];
    21.             if(j >= v[i]) f[i][j] += f[i][j - v[i]];
    22.         }
    23.     
    24.     cout << f[4][m] << endl;
    25.     
    26.     return 0;
    27. }

    优化：

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 1010;
    6. ​
    7. int v[5] = {0, 10, 20, 50, 100};
    8. int f[N];
    9. ​
    10. int main()
    11. {
    12.     int m;
    13.     cin >> m;
    14.     
    15.     f[0] = 1;
    16.     
    17.     for(int i = 1;i <= n; i++)
    18.         for(int j = 0;j <= m; j++)
    19.         {
    20.             if(j >= v[i]
    21.                f[j] += f[j - v[i]];
    22.         }
    23.     
    24.     cout << f[m] << endl;
    25.     
    26.     return 0;
    27. }

    11.背包问题求具体方案

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

    第 i 件物品的体积是 vi，价值是 wi。

    求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

    输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。

    输入格式

    第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

    接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 1010;
    6. ​
    7. int n, m;
    8. int v[N], w[N];
    9. int f[N][N];
    10. ​
    11. int main()
    12. {
    13.     cin >> n >> m;
    14.     
    15.     for(int i = 1;i <= n; i++) cin >> v[i] >> w[i];
    16.     
    17.     for(int i = n;i >= 1; i--)
    18.     {
    19.         for(int j = 0;j <= m; j++)
    20.         {
    21.             f[i][j] = f[i + 1][j];
    22.             if(j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
    23.         }
    24.     }
    25.     
    26.     int j = m;
    27.     for(int i = 1;i <= n; i++)
    28.         if(j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
    29.         {
    30.             cout << i << ' ';
    31.             j -= v[i];
    32.         }
    33.     
    34.     return 0;
    35. }

    12.分组背包问题

    有 N 组物品和一个容量是 V 的背包。

    每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

    求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

    输出最大价值。

    第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

    接下来有 NN 组数据：

    • 每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；

    • 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 110;
    6. ​
    7. int n, m;
    8. int f[N];
    9. ​
    10. int main()
    11. {
    12.     cin >> n >> m;
    13.     for(int i = 1;i <= n; i++)
    14.     {
    15.         
    16.     }
    17.     return 0;
    18. }

    13.机器分配

    总公司拥有M台相同的高效设备，准备分给下属的N个分公司。

    每个分公司若获得这些设备，可以为国家提供一定的盈利，盈利预分配的设备数量有关。

    问：如何分配这M台设备才能使国家得到盈利最大？

    求出最大盈利值。

    分配原则：每个公司有权获得热议数目的设备，但是总台数不超过设备数M。

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 11, M = 16;
    7. ​
    8. int n, m;
    9. int w[N][M]
    10. int f[N][M];
    11. int way[N];
    12. ​
    13. int main()
    14. {
    15.     cin >> n >> m;
    16.     for(int i = 1;i <= n; i++)
    17.         for(int j = 1;j <= m; j++)
    18.             cin >> w[i][j];
    19.     
    20.     for(int i = 1;i <= n; i++)
    21.         for(int j = m;j >= 0; j--)
    22.         {
    23.             f[i][j] = f[i - 1][j];
    24.             for(int k = 1;k <= j; k++)
    25.                 f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i]);
    26.         }
    27.     
    28.     cout << f[n][m] << endl;
    29.     
    30.     int j = m;
    31.     for(int n; i; i--)
    32.         for(int k = 0;k <= j; k++)
    33.             if(f[i][k] == f[i - 1][j - k] + w[i][k])
    34.             {
    35.                 way[i] = k;
    36.                 j -= k;
    37.                 break;
    38.             }
    39.     
    40.     for(int i = 1;i <= n; i++)
    41.         cout << i << ' ' << way[i] << endl;
    42.     return 0;
    43. }

    14.金明的预算方案

    金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。

    更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。

    今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

    QQ截图20190313024710.png

    如果要买归类为附件的物品，必须先买该附件所属的主件。

    每个主件可以有0个、1个或2个附件。

    附件不再有从属于自己的附件。

    金明想买的东西很多，肯定会超过妈妈限定的N元。

    于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。

    他还从因特网上查到了每件物品的价格（都是10元的整数倍）。

    他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

    设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，…，jk，则所求的总和为：

    v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk]（其中*为乘号）

    请你帮助金明设计一个满足要求的购物单。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. ​
    6. #define v first
    7. #define w second
    8. ​
    9. using namespace std;
    10. ​
    11. typedef pair<int, int> PII;
    12. ​
    13. const int N = 60, M = 32010;
    14. ​
    15. int n, m;
    16. PII master[N];
    17. vector servent[N];
    18. int f[M];
    19. ​
    20. int main()
    21. {
    22.     cin >> m >> n;
    23. ​
    24.     for (int i = 1; i <= n; i ++ )
    25.     {
    26.         int v, p, q;
    27.         cin >> v >> p >> q;
    28.         p *= v;
    29.         if (!q) master[i] = {v, p};
    30.         else servent[q].push_back({v, p});
    31.     }
    32. ​
    33.     for (int i = 1; i <= n; i ++ )
    34.         for (int u = m; u >= 0; u -- )
    35.         {
    36.             for (int j = 0; j < 1 << servent[i].size(); j ++ )
    37.             {
    38.                 int v = master[i].v, w = master[i].w;
    39.                 for (int k = 0; k < servent[i].size(); k ++ )
    40.                     if (j >> k & 1)
    41.                     {
    42.                         v += servent[i][k].v;
    43.                         w += servent[i][k].w;
    44.                     }
    45.                 if (u >= v) f[u] = max(f[u], f[u - v] + w);
    46.             }
    47.     }
    48. ​
    49.     cout << f[m] << endl;
    50. ​
    51.     return 0;
    52. }

    15.开心的金明

    金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。

    更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。

    今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。

    于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1∼5 表示，第 5 等最重要。

    他还从因特网上查到了每件物品的价格（都是整数元）。

    他希望在不超过 NN 元（可以等于 NN 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 

    设第 jj 件物品的价格为 v[j]v[j]，重要度为 w[j]，共选中了 k 件物品，编号依次为 j1，j2，…，jk，则所求的总和为： 

    v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]

    请你帮助金明设计一个满足要求的购物单。

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 30010;
    7. ​
    8. int n, m;
    9. int f[N];
    10. ​
    11. int main()
    12. {
    13.     cin >> m >> n;
    14.     for(int i = 0;i < n; i++)
    15.     {
    16.         int v, w;
    17.         cin >> v >> w;
    18.         for(int j = m;j >= v; j--)
    19.             f[j] = max(f[j], f[j - v] + v * w);
    20.     }
    21.     
    22.     cout << f[m] << endl;
    23.     
    24.     return 0;
    25. }

    16.货币系统

    给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。

    3 10

    1

    2

    5

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. typedef long long LL;
    6. ​
    7. const int N = 3010;
    8. ​
    9. int n, m;
    10. LL f[N];
    11. ​
    12. int main()
    13. {
    14.     cin >> n >> m;
    15.     
    16.     f[0] = 1;
    17.     for(int i = 0;i < n; i++)
    18.     {
    19.         int a;
    20.         cin >> a;
    21.         for(int j = a;j <= m; j++)
    22.             f[j] += f[j - a];
    23.     }
    24.     
    25.     cout << f[m] << endl;
    26.     
    27.     return 0;
    28. }

    17.货币系统2

    在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。

    为了方便，我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。 

    在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。

    然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。

    例如在货币系统 n=3, a=[2,5,9] 中，金额 1,3 就无法被表示出来。 

    两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 

    现在网友们打算简化一下货币系统。

    他们希望找到一个货币系统 (m,b)，满足 (m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。

    他们希望你来协助完成这个艰巨的任务：找到最小的 m。

    性质1：a1，a2，.....，an一定都可以被表示出来

    性质2：在最优解中，b1，b2，.....，bm一定都是从a1，a2，...，an中选择的

    性质3：b1，b2，....，bm一定不能被其他bi表示出来

    1. #include
    2. #include
    3. #include
    4. ​
    5. using namespace std;
    6. ​
    7. const int N = 25010;
    8. ​
    9. int n;
    10. int a[N];
    11. int f[N];
    12. ​
    13. int main()
    14. {
    15.     int T;
    16.     cin >> T;
    17.     
    18.     while(T--)
    19.     {
    20.         cin >> n;
    21.         for(int i = 0;i < n; i++) cin >> a[i];
    22.         sort(a, a + n);
    23.         
    24.         int m = a[n-1];
    25.         memset(f, 0, sizeof(f));
    26.         f[0] = 1;
    27.         
    28.         int res = 0;
    29.         for(int i = 0;i < n; i++)
    30.         {
    31.             if(!f[a[i]]) res++;
    32.             for(int j = a[i];j <= m; j++)
    33.                 f[j] += f[j - a[i]];
    34.         }
    35.         
    36.         cout << res << endl;
    37.     }
    38.     return 0;
    39. }

    18.混合背包问题

    有 N 种物品和一个容量是 V 的背包。

    物品一共有三类：

    第一类物品只能用1次（01背包）；

    第二类物品可以用无限次（完全背包）；

    第三类物品最多只能用 si 次（多重背包）；

    每种体积是 vi，价值是 wi。

    求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

    1. #include
    2. ​
    3. using namespace std;
    4. ​
    5. const int N = 1010;
    6. ​
    7. int n, m;
    8. int f[N];
    9. ​
    10. int main()
    11. {
    12.     cin >> n >> m;
    13.     for(int i = 0;i < n; i++)
    14.     {
    15.         int v, w, s;
    16.         cin >> v >> w >> s;
    17.         if(s == 0)//完全背包问题
    18.         {
    19.             for(int j = v;j <= m; j++)
    20.                 f[j] = max(f[j], f[j - v] + w);
    21.         }
    22.         else
    23.         {
    24.             if(s == -1) s = 1;
    25.             for(int k = 1;k <= s; k *= 2)
    26.             {
    27.                 for(int j = m;j >= k * v; j--)
    28.                     f[j] = max(f[j], f[j - k * v] + k * w);
    29.                 s -= k;
    30.             }
    31.             if(s)
    32.             {
    33.                 for(int j = m;j >= s * v; j--)
    34.                     f[j] = max(f[j], f[j - s * v] + s * w);
    35.             }
    36.         }
    37.     }
    38.     
    39.     cout << f[m] << endl;
    40.     
    41.     return 0;
    42. }

    19.有依赖的背包问题

    有 N 个物品和一个容量是 V 的背包。

    物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

    如下图所示：

    QQ图片20181018170337.png

    如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

    每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。

    求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

    输出最大价值。

    输入格式

    第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

    接下来有 N 行数据，每行数据表示一个物品。 第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。 如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。

    1. #include
    2. #include
    3. #include
    4. ​
    5. using namespace std;
    6. ​
    7. const int N = 110;
    8. ​
    9. int n, m;
    10. int v[N], w[N];
    11. int h[N], e[N], ne[N], idx;
    12. int f[N][N];
    13. ​
    14. void add(int p, int i)
    15. {
    16.     e[idx] = i;
    17.     ne[idx] = h[p];
    18.     h[p] = idx++;
    19. }
    20. ​
    21. void dfs(int u)
    22. {
    23.     for(int i = h[u]; ~i; i = ne[i]) //循环物品组
    24.     {
    25.         int son = e[i];
    26.         dfs(e[i]);
    27.         
    28.         //分组背包
    29.         for(int j = m - v[u];j >= 0; j--)//循环体积
    30.             for(int k = 0;k <= j; k++)//循环决策
    31.                 f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
    32.     }
    33.     
    34.     //将物品v加进去
    35.     for(int i = m;i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
    36.     for(int i = 0;i < v[u]; i++) f[u][i] = 0;
    37. }
    38. ​
    39. int main()
    40. {
    41.     cin >> n >> m;
    42.     
    43.     memset(h, -1, sizeof(h));
    44.     int root;
    45.     for(int i = 1;i <= n; i++)
    46.     {
    47.         int p;
    48.         cin >> v[i] >> w[i] >> p;
    49.         
    50.         if(p == -1) root = i;
    51.         else add(p, i);
    52.     }
    53.     
    54.     dfs(root);
    55.     
    56.     cout << f[root][m] << endl;
    57.     return 0;
    58. }

    代码：

    1. #include 
    2. #include 
    3. #include 
    4. #define init() memset(h,-1,sizeof h);
    5. using namespace std;
    6. const int N=1005;
    7. int dp[N][N];
    8. int v[N];
    9. int w[N];
    10. int e[N],idx,ne[N],h[N];
    11. void add(int a,int b)
    12. {
    13.     e[idx]=b;
    14.     ne[idx]=h[a];
    15.     h[a]=idx++;
    16. }
    17. int n,m;
    18. void dfs(int u)
    19. {
    20.     
    21.     for(int i=h[u];~i;i=ne[i])
    22.     {
    23.         int son=e[i];
    24.         dfs(son);
    25.         //这个版本默认还没有选择u,所以要预留空间给u
    26.         for(int j=m-v[u];j>=0;j--)   //预留空间v[u],选择范围[m-v[u],0]
    27.             for(int k=0;k<=j;k++)   //分配给子树空间就没有限制了
    28.                 dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[son][k]);
    29.     }
    30.     //从后往前递推,表示的是上一次的状态
    31.     for(int i=m;i>=v[u];i--) dp[u][i]=dp[u][i-v[u]]+w[u];
    32.     for(int i=0;i//所有不到v[u]的集合，值都必须删除
    33.         dp[u][i]=0;
    34. }
    35. int main()
    36. {
    37.     init();
    38.     cin>>n>>m;
    39.     int root;
    40.     for(int i=1;i<=n;i++)
    41.     {
    42.         int p;
    43.         cin>>v[i]>>w[i]>>p;
    44.         if(p==-1) root=i;
    45.         else add(p,i);
    46.     }
    47.     
    48.     dfs(root);
    49.     cout<
    50. }

    20.背包问题求方案数

    有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

    第 i 件物品的体积是 vi，价值是 wi。

    求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

    输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7 的结果。

    输入格式

    第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

    接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

    1. #include
    2. #include
    3. #include
    4. ​
    5. using namespace std;
    6. ​
    7. const int N = 1010, mod = 1e9 + 7;
    8. ​
    9. int n, m;
    10. int f[N], g[N];
    11. ​
    12. int main()
    13. {
    14.     cin >> n >> m;
    15.     
    16.     memset(f, -0x3f, sizeof(f));
    17.     f[0] = 0;
    18.     g[0] = 1;
    19.     
    20.     for(int i = 0;i < n; i++)
    21.     {
    22.         int v, w;
    23.         cin >> v >> w;
    24.         for(int j = m;j >= v; j--)
    25.         {
    26.             int maxv = max(f[j], f[j - v] + w);
    27.             int cnt = 0;
    28.             if(maxv == f[j]) cnt += g[j];
    29.             if(maxv == f[j - v] + w) cnt += g[j - v];
    30.             g[j] = cnt % mod;
    31.             f[j] = maxv;
    32.         }
    33.     }
    34.     
    35.     int res = 0;
    36.     for(int i = 0;i <= m; i++)
    37.         res = max(res, f[i]);
    38.     
    39.     int cnt = 0;
    40.     
    41.     for(int i = 0;i <= m; i++)
    42.         if(res == f[i])
    43.             cnt = (cnt + g[i]) % mod;
    44.     
    45.     cout << cnt << endl;
    46.     
    47.     return 0;
    48. }

    21.能量石

    岩石怪物杜达生活在魔法森林中，他在午餐时收集了 N 块能量石准备开吃。

    由于他的嘴很小，所以一次只能吃一块能量石。

    能量石很硬，吃完需要花不少时间。

    吃完第 i 块能量石需要花费的时间为 Si 秒。

    杜达靠吃能量石来获取能量。

    不同的能量石包含的能量可能不同。

    此外，能量石会随着时间流逝逐渐失去能量。

    第 ii 块能量石最初包含 Ei 单位的能量，并且每秒将失去 Li 单位的能量。

    当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

    能量石中包含的能量最多降低至 0。

    请问杜达通过吃能量石可以获得的最大能量是多少？

    输入格式

    第一行包含整数 TT，表示共有 TT 组测试数据。

    每组数据第一行包含整数 NN，表示能量石的数量。

    接下来 N 行，每行包含三个整数 Si,Ei,Li。

    1. #include
    2. #include
    3. #include
    4. ​
    5. using namespace std;
    6. ​
    7. const int N = 10010;
    8. ​
    9. int n;
    10. struct Stone
    11. {
    12.     int s, e, l;
    13.     bool operator< (const Stone &W) const
    14.     {
    15.         return s * W.l < l * W.s;
    16.     }
    17. }stone[N];
    18. int f[N];
    19. ​
    20. int main()
    21. {
    22.     int T;
    23.     cin >> T;
    24.     for(int i = 1;i <= T; i++)
    25.     {
    26.         int m = 0;
    27.         cin >> n;
    28.         for(int j = 0;j < n; j++)
    29.         {
    30.             int s, e, l;
    31.             cin >> s >> e >> l;
    32.             stone[j] = {s, e, l};
    33.             m += s;
    34.         }
    35.         
    36.         sort(stone, stone + n);
    37.         
    38.         memset(f, -0x3f, sizeof(f));
    39.         f[0] = 0;
    40.         
    41.         for(int j = 0;j < n; j++)
    42.         {
    43.             int s = stone[j].s, e = stone[j].e, l = stone[j].l;
    44.             for(int k = m;k >= s; k--)
    45.                 f[k] = max(f[k], f[k - s] + e - (k - s) * l);
    46.         }
    47.         
    48.         int res = 0;
    49.         for(int i = 0;i <= m; i++) res = max(res, f[i]);
    50.         printf("Case #%d: %d\n", i, res);
    51.     }
    52.     
    53.     return 0;
    54. }

  • 相关阅读:
    SCAN BASIC --- PARTI basic and fault model
    Linux中报错no space device解决思路
    【MySQL篇】 MySQL基础学习
    Java Random类生成随机数示例分析
    商城项目20_sku在es中储存模型分析、索引建立、上架逻辑、核心上架、流程图
    深度强化学习 第 4 章 DQN 与 Q 学习
    java-net-php-python-jsp祥生房屋租赁管理系统演示录像2019计算机毕业设计程序
    P1455 搭配购买（01背包&并查集）
    mysql全文索引
    kafka—分区的分配和再平衡
  • 原文地址：https://blog.csdn.net/Williamtym/article/details/134012443