华为校招机试 - 攻城战（Java & JS & Python）

怼烎@ 2024-03-26 16:35 57阅读 0赞

**目录**

题目描述

输入描述

输出描述

用例

题目解析

JavaScript算法源码

Java算法源码

Python算法源码

--------------------

#### 题目描述 ####

一支攻城部队， 有若干种大炮各座， 以及数量有限的火药，每种大炮的威力不尽相同，且在每次开火之前都需要一定时间填充火药， 请你帮助指挥官在给定的时间结束之前或者火药存量耗尽之前给予城池最大的打击。

约束：

1.  大炮每次开火的威力一样；
2.  火药剩余量不小于大炮的消耗量，该大炮才能开火；
3.  填充火药之外的时间忽略不计；
4.  不同种大炮可以同时开火。

#### 输入描述 ####

第一行，整数 N ， M ， T

*  N 表示大炮种类个数
 *  M 表示火药数量，
 *  T 表示攻城时间
 *  1 ≤ N,M,T ≤1000

接下来 N 行，每一行三个整数 A ， B ， C

*  A 表示大炮的威力
 *  B 表示大炮每次攻击消耗的火药量
 *  C 表示大炮每次攻击填充火药的时间
 *  0 ≤ A,B,C ≤ 100000。

#### 输出描述 ####

输出在给定的时间结束之前或者火药存量耗尽之前给予城池最大的打击。

#### 用例 ####

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">3 100 20<br> 10 8 5<br> 5 2 1<br> 20 25 8</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">160</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p>总共有&nbsp;3&nbsp;种大炮，火药存量&nbsp;100 ， 攻城时间&nbsp;20 ;</p> <p>第&nbsp;1&nbsp;种大炮威力&nbsp;10 ，每次攻击消耗火药&nbsp;8&nbsp;，每次攻击填充火药时间&nbsp;5&nbsp;；</p> <p>第&nbsp;2&nbsp;种大炮威力&nbsp;5&nbsp;，每次攻击消耗火药&nbsp;2&nbsp;，每次攻击填充火药时间&nbsp;1&nbsp;；</p> <p>第&nbsp;3&nbsp;种大炮威力&nbsp;20 ，每次攻击消耗火药&nbsp;25 ，每次攻击填充火药时间&nbsp;8&nbsp;；</p> </td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:86px;">输入</td> 
   <td style="width:412px;">2 10 10<br> 1 1 1<br> 2 2 2</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">输出</td> 
   <td style="width:412px;">10</td> 
  </tr> 
  <tr> 
   <td style="width:86px;">说明</td> 
   <td style="width:412px;"> <p>总共有&nbsp;2&nbsp;种大炮，火药存量&nbsp;10 ，攻城时间&nbsp;10 ；</p> <p>第&nbsp;1&nbsp;种大炮威力&nbsp;1&nbsp;，每次攻击消耗火药&nbsp;1&nbsp;，每次攻击填充火药时间&nbsp;1&nbsp;；</p> <p>第&nbsp;2&nbsp;种大炮威力&nbsp;2&nbsp;，每次攻击消耗火药&nbsp;2&nbsp;，每次攻击填充火药时间&nbsp;2&nbsp;；</p> </td> 
  </tr> 
 </tbody> 
</table>

#### 题目解析 ####

本题首先需要理解这句话：

> 不同种大炮可以同时开火。

这说明不同种大炮可以同时装填火药。

原因是：我们可以假设不同种大炮不能同时装填火药的话，即只能依次装填的话，那么无法做到同时开火。

这句话的理解很关键，因为这会将题目从“二维费用完全背包问题”变成“多重背包问题”。

> PS：如果你想了解这两个背包问题，请先弄懂：
> 
>  *  01背包问题：[算法设计 - 01背包问题\_01背包问题算法\_伏城之外的博客-CSDN博客][- 01_01_-CSDN]
>  *  01背包问题的滚动数组优化，完全背包问题：[算法设计 - 01背包问题的状态转移方程优化，以及完全背包问题\_伏城之外的博客-CSDN博客][- 01_-CSDN]

何为“二维费用背包问题”？

> 有N种物品，每种物品只有1件，第 i 种物品的重量为wi，体积为vi，价值为pi，现在有一个承重为W，容量为V的背包，请问：在不超过背包承重和容量的前提下，背包所能装入物品的最大价值？

何为“二维费用完全背包问题”

> 有N种物品，每种物品只有无数件，第 i 种物品的重量为wi，体积为vi，价值为pi，现在有一个承重为W，容量为V的背包，请问：在不超过背包承重和容量的前提下，背包所能装入物品的最大价值？

本题，如果不同种大炮不能同时开火的话，则是“二维费用完全背包问题”，对应关系如下：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>N种大炮</td> 
   <td>N种物品</td> 
  </tr> 
  <tr> 
   <td>总火药数量M</td> 
   <td>背包承重W</td> 
  </tr> 
  <tr> 
   <td>总攻城时间T</td> 
   <td>背包容量V</td> 
  </tr> 
  <tr> 
   <td>第 i 种大炮每次攻击消耗的火药量Bi</td> 
   <td>第 i 种物品的重量wi</td> 
  </tr> 
  <tr> 
   <td>第 i 种大炮每次攻击填充火药的时间Ci</td> 
   <td>第 i 种物品的重量vi</td> 
  </tr> 
  <tr> 
   <td>第 i 种大炮的威力Ai&nbsp;</td> 
   <td>第 i 种物品的价值pi</td> 
  </tr> 
 </tbody> 
</table>

何为“多重背包问题”

> 有N种物品，第 i 种物品的重量为wi，价值为pi，件数为si，现在有一个承重为W，请问：在不超过背包承重和容量的前提下，背包所能装入物品的最大价值？

本题，由于不同种大炮可以同时开火，因此是“多重背包问题”，对应关系如下：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>N种大炮&nbsp;</td> 
   <td>N种物品</td> 
  </tr> 
  <tr> 
   <td>总火药数量M</td> 
   <td>背包承重W</td> 
  </tr> 
  <tr> 
   <td>第 i 种大炮每次攻击消耗的火药量Bi</td> 
   <td>第 i 种物品的重量wi</td> 
  </tr> 
  <tr> 
   <td>第 i 种大炮的威力Ai</td> 
   <td>第 i 种物品的价值pi</td> 
  </tr> 
  <tr> 
   <td>第 i 种大炮的最大数量 T / Ci</td> 
   <td>第 i 种物品的件数si</td> 
  </tr> 
 </tbody> 
</table>

多重背包问题的求解，可以基于01背包的状态转移方程进行衍生拓展得出。

何为01背包问题

> 有N种物品，每种物品只有1件，第 i 种物品的重量为wi，价值为pi，现在有一个承重为W，请问：在不超过背包承重和容量的前提下，背包所能装入物品的最大价值？

01背包问题的状态转移方程，有基于二维数组：

dp\[ i \]\[ j \] = max( dp\[ i-1 \]\[ j \], dp\[ i-1 \]\[ j - wi \] + pi )

dp\[i\]\[j\]的含义是：背包承重为 j 时，可选物品为第 0 ~ i 种，背包所有能装入的最大价值。

*  对于第 i 种物品不选的话，dp\[i\]\[j\] = dp\[ i-1 \]\[ j \]；因为不选的话，背包的承重 j 不会改变，背包的总价值也不会改变。
 *  对于第 i 种物品选的话，dp\[i\]\[j\] = dp\[ i-1 \]\[ j - wi \] + pi；因为选了的话，背包承重 j 就会减少wi的承重，但是背包的总价值就会增加 pi。

01背包问题的状态转移方程，可以进行滚动数组优化，即将方程种二维数组压缩为一维数组：

dp\[ j \] = max( dp\[ j \], dp\[ j - wi \] + pi )

即去除了dp的物品范围维度，或者说总是只保留最后一个被选择物品的维度。更多关于01背包的滚动数组优化，请看：[算法设计 - 01背包问题的状态转移方程优化，以及完全背包问题\_伏城之外的博客-CSDN博客][- 01_-CSDN]

需要特别注意的是，使用滚动数组的话，则背包承重 j 的遍历需要反向遍历。

多重背包问题的求解有两种方式：

*  朴素方法
 *  二进制优化方法

其中，朴素方法，即将”多重背包问题“转化为”01背包问题“，比如

以上多重背包的表格表示，其实我们可以将其转化为”01背包“表示

即将：多重背包的”一种物品多件“ 转为为 ”多种物品一件“。

因此多重背包的朴素求解，只是在01背包的基础上，扩展了物品种类的数量，但是扩展出来的物品种类的价值和重量都是一样的。

但是朴素方法也有一个弊端，那就是当物品数量很多时，则会扩展出非常多的物品种类，此时需要进行优化，这里推荐使用二进制优化。

什么是二进制优化呢？

我们先来通过一个例子来引出，

0 0 0 0 0 0 0 1 ---> 2^0 = 1  
0 0 0 0 0 0 1 0 ---> 2^1 = 2  
0 0 0 0 0 1 0 0 ---> 2^2 = 4  
0 0 0 0 1 0 0 0 ---> 2^3 = 8  
0 0 0 1 0 0 0 0 ---> 2^4 = 16  
0 0 1 0 0 0 0 0 ---> 2^5 = 32  
0 1 0 0 0 0 0 0 ---> 2^6 = 64  
1 0 0 0 0 0 0 0 ---> 2^7 = 128

通过上面列出的数1,2,4,8,16,32,64,128，我们可以表达出1~255之间的所有数，原因是1~255之间就是00000001 ~ 11111111 这两个二进制数之间所有的数。

因此，我们可以通过从8个数（1,2,4,8,16,32,64,128）中选择一个或多个数，组合求和表示出1~255的255个数。

这就是二进制优化。

那么如果我们需要表达1~1000之间的所有数呢？

0 0 0 0 0 0 0 0 0 1 ---> 2^0 = 1  
0 0 0 0 0 0 0 0 1 0 ---> 2^1 = 2  
0 0 0 0 0 0 0 1 0 0 ---> 2^2 = 4  
0 0 0 0 0 0 1 0 0 0 ---> 2^3 = 8  
0 0 0 0 0 1 0 0 0 0 ---> 2^4 = 16  
0 0 0 0 1 0 0 0 0 0 ---> 2^5 = 32  
0 0 0 1 0 0 0 0 0 0 ---> 2^6 = 64  
0 0 1 0 0 0 0 0 0 0 ---> 2^7 = 128  
0 1 0 0 0 0 0 0 0 0 ---> 2^8 = 256  
1 0 0 0 0 0 0 0 0 0 ---> 2^9 = 512

上面10个数（1，2，4，8，16，32，64，128，256，512）可组合的最大数为1023，可以发现，此时范围不是我们需要的，我们只需要1~1000，而现在范围是1~1023。

有没有办法使用二进制优化准确的表示1~1000呢？

由于上面10个数中512是导致范围顶到1023的原因，因此我们不能要512，此时二进制数如下：

但是上面这个范围只能表示到1~511，还差489，而489的二进制数为000111101001，我们将489加入，此时有如下数：

上面10个数可以表达1~1000任意数吗？

比如490 = 489 + 1

比如512 = 489 + 16 + 4 + 2 + 1

大家可以试试，上面10个数确实可以表达出1~1000的任意数。

那么对于多重背包，该如何使用二进制优化呢？

我们已经知道了使用多个二进制数，可以组合表达出更大范围的任意数，而当前多重背包问题，是将”一种物品N件“转化为”N种物品一件“，之后使用01背包的方式求解，即N种物品，遍历每个物品，进行”选” 与 “不选” 的抉择。

这种方式相当于用N个1组合出1~N的任意数。这是极其低效的。

其实这N中物品的价值和重量都是相同的，我们完全使用二进制优化，来组合出1~N的任意数。具体操作方法请看源码。

#### JavaScript算法源码 ####

朴素方法求解

/* JavaScript Node ACM模式 控制台输入获取 */
    const { get } = require("http");
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    const lines = [];
    let n, m, t;
    rl.on("line", (line) => {
      lines.push(line);
    
      if (lines.length === 1) {
        [n, m, t] = lines[0].split(" ").map(Number);
      }
    
      if (n !== undefined && lines.length === n + 1) {
        lines.shift();
        const guns = lines.map((line) => line.split(" ").map(Number));
        console.log(getResult(n, m, t, guns));
        lines.length = 0;
      }
    });
    
    /**
     * @param {*} n 大炮种类
     * @param {*} m 火药总量
     * @param {*} t 总时间
     * @param {*} guns 各种大炮参数 [大炮的威力， 大炮消耗的火药量， 大炮装填火药的时间]
     */
    function getResult(n, m, t, guns) {
      const a = new Array(n + 1).fill(0); // a[i] 表示 第 i 种大炮的威力
      const b = new Array(n + 1).fill(0); // b[i] 表示 第 i 种大炮每次攻击需要消耗的火药量
      const c = new Array(n + 1).fill(0); // c[i] 表示 第 i 种大炮在规定时间t内，最多可以开几炮
    
      for (let i = 1; i <= n; i++) {
        a[i] = guns[i - 1][0];
        b[i] = guns[i - 1][1];
        c[i] = Math.floor(t / guns[i - 1][2]);
      }
    
      const dp = new Array(m + 1).fill(0);
    
      // 遍历每种大炮
      for (let i = 1; i <= n; i++) {
        // 总火药量
        for (let j = m; j >= b[i]; j--) {
          // 大炮装填次数
          for (let k = 1; k <= c[i]; k++) {
            // 只有总火药量 j 足够，即 j >= b[i] * k,才能开火
            if (j >= b[i] * k) {
              // 遍历到大炮i，可以选，可以不选, 如果不选的话，则此时最大总威力保持不变, 如果选的话，则此时最大总威力 + a[i] * k，但是总火药量j减少b[i] * k
              dp[j] = Math.max(dp[j], dp[j - b[i] * k] + a[i] * k);
            }
          }
        }
      }
    
      return dp[m];
    }

二进制优化求解

/* JavaScript Node ACM模式 控制台输入获取 */
    const { get } = require("http");
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    const lines = [];
    let n, m, t;
    rl.on("line", (line) => {
      lines.push(line);
    
      if (lines.length === 1) {
        [n, m, t] = lines[0].split(" ").map(Number);
      }
    
      if (n !== undefined && lines.length === n + 1) {
        lines.shift();
        const guns = lines.map((line) => line.split(" ").map(Number));
        console.log(getResult(n, m, t, guns));
        lines.length = 0;
      }
    });
    
    /**
     * @param {*} n 大炮种类
     * @param {*} m 火药总量
     * @param {*} t 总时间
     * @param {*} guns 各种大炮参数 [大炮的威力， 大炮消耗的火药量， 大炮装填火药的时间]
     */
    function getResult(n, m, t, guns) {
      const tmp_a = new Array(n + 1).fill(0);
      const tmp_b = new Array(n + 1).fill(0);
      const tmp_c = new Array(n + 1).fill(0);
    
      for (let i = 1; i <= n; i++) {
        tmp_a[i] = guns[i - 1][0]; // tmp_a[i] 表示 第 i 种大炮的威力
        tmp_b[i] = guns[i - 1][1]; // 表示 第 i 种大炮每次攻击需要消耗的火药量
        tmp_c[i] = Math.floor(t / guns[i - 1][2]); // 表示 第 i 种大炮在规定时间t内，最多可以开几炮，相当于多重背包问题中物品的件数
      }
    
      // tmp_a 使用二进制优化 扩展行后变为 a
      const a = [];
      // tmp_b 使用二进制优化 扩展行后变为b
      const b = [];
    
      // 使用二进制优化，扩展行
      for (let i = 1; i <= n; i++) {
        // // 注意这里 j 是二进制数，对应物品的件数，通过左移运算，得到1，2，4，8.。。这样的二进制数
        for (let j = 1; j <= tmp_c[i]; j <<= 1) {
          // 将一种物品多件，变为一种物品一件，即：
          a.push(tmp_a[i] * j); // 老大炮的威力 * 多件 = 新大炮种类的威力
          b.push(tmp_b[i] * j); // 老大炮的火药消耗 * 多件 = 新大炮种类的火药消耗
          tmp_c[i] -= j; // 注意，老大炮的总件数 减少 j
        }
    
        // 比如需要二进制数组合出1~1000范围任意数，则此时最后一个数489无法使用2^n表示，只能单独作为一个数存在
        if (tmp_c[i] != 0) {
          a.push(tmp_a[i] * tmp_c[i]);
          b.push(tmp_b[i] * tmp_c[i]);
        }
      }
    
      // 扩展行后，大炮种类变多，更新n
      n = a.length;
    
      // 下面就是01背包的解题思路了，这里使用了滚动数组，因此背包承重（即本题总火药量）要反向遍历
      const dp = new Array(m + 1).fill(0);
      for (let i = 0; i < n; i++) {
        for (let j = m; j >= b[i]; j--) {
          dp[j] = Math.max(dp[j], dp[j - b[i]] + a[i]);
        }
      }
    
      return dp[m];
    }

#### Java算法源码 ####

朴素方法求解

import java.util.Scanner;
    
    public class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    
        int n = sc.nextInt();
        int m = sc.nextInt();
        int t = sc.nextInt();
    
        int[] a = new int[n + 1];
        int[] b = new int[n + 1];
        int[] c = new int[n + 1];
    
        for (int i = 1; i <= n; i++) {
          a[i] = sc.nextInt(); // a[i] 表示 第 i 种大炮的威力
          b[i] = sc.nextInt(); // b[i] 表示 第 i 种大炮每次攻击需要消耗的火药量
          c[i] = t / sc.nextInt(); // c[i] 表示 第 i 种大炮在规定时间t内，最多可以开几炮，相当于多重背包问题中物品的件数
        }
    
        System.out.println(getResult(n, m, t, a, b, c));
      }
    
      /**
       * @param n 大炮种类个数
       * @param m 总火药数量
       * @param t 总时间
       * @param a a[i] 表示 第 i 种大炮的威力
       * @param b b[i] 表示 第 i 种大炮每次攻击需要消耗的火药量
       * @param c 表示 第 i 种大炮在规定时间t内，最多可以开几炮，相当于多重背包问题中物品的件数
       * @return 在给定的时间结束之前或者火药存量耗尽之前给予城池最大的打击
       */
      public static int getResult(int n, int m, int t, int[] a, int[] b, int[] c) {
        int[] dp = new int[m + 1];
    
        for (int i = 1; i <= n; i++) { // 遍历每种大炮
          for (int j = m; j >= b[i]; j--) { // 总火药量
            for (int k = 1; k <= c[i]; k++) { // 大炮装填次数
              // 只有总火药量 j 足够，即 j >= b[i] * k,才能开火
              if (j >= b[i] * k) {
                // 遍历到大炮i，可以选，可以不选, 如果不选的话，则此时最大总威力保持不变, 如果选的话，则此时最大总威力 + a[i] * k，但是总火药量j减少b[i] * k
                dp[j] = Math.max(dp[j], dp[j - b[i] * k] + a[i] * k);
              }
            }
          }
        }
    
        return dp[m];
      }
    }

二进制优化求解

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    
        int n = sc.nextInt();
        int m = sc.nextInt();
        int t = sc.nextInt();
    
        int[] tmp_a = new int[n + 1];
        int[] tmp_b = new int[n + 1];
        int[] tmp_c = new int[n + 1];
    
        for (int i = 1; i <= n; i++) {
          tmp_a[i] = sc.nextInt(); // tmp_a[i] 表示 第 i 种大炮的威力
          tmp_b[i] = sc.nextInt(); // tmp_b[i] 表示 第 i 种大炮每次攻击需要消耗的火药量
          tmp_c[i] = t / sc.nextInt(); // tmp_c[i] 表示 第 i 种大炮在规定时间t内，最多可以开几炮，相当于多重背包问题中物品的件数
        }
    
        System.out.println(getResult(n, m, t, tmp_a, tmp_b, tmp_c));
      }
    
      /**
       * @param n 大炮种类数
       * @param m 总火药数
       * @param t 总时间
       * @param tmp_a tmp_a[i] 表示 第 i 种大炮的威力
       * @param tmp_b tmp_b[i] 表示 第 i 种大炮每次攻击需要消耗的火药量
       * @param tmp_c tmp_c[i] 表示 第 i 种大炮在规定时间t内，最多可以开几炮，相当于多重背包问题中物品的件数
       * @return 在给定的时间结束之前或者火药存量耗尽之前给予城池最大的打击
       */
      public static int getResult(int n, int m, int t, int[] tmp_a, int[] tmp_b, int[] tmp_c) {
        // tmp_a 使用二进制优化 扩展行后变为 a
        ArrayList<Integer> a = new ArrayList<>();
        // tmp_b 使用二进制优化 扩展行后变为b
        ArrayList<Integer> b = new ArrayList<>();
    
        // 使用二进制优化，扩展行
        for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= tmp_c[i]; j <<= 1) { // 注意这里 j 是二进制数，对应物品的件数，通过左移运算，得到1，2，4，8.。。这样的二进制数
            // 将一种物品多件，变为一种物品一件，即：
            a.add(tmp_a[i] * j); // 老大炮的威力 * 多件 = 新大炮种类的威力
            b.add(tmp_b[i] * j); // 老大炮的火药消耗 * 多件 = 新大炮种类的火药消耗
            tmp_c[i] -= j; // 注意，老大炮的总件数 减少 j
          }
    
          // 比如需要二进制数组合出1~1000范围任意数，则此时最后一个数489无法使用2^n表示，只能单独作为一个数存在
          if (tmp_c[i] != 0) {
            a.add(tmp_a[i] * tmp_c[i]);
            b.add(tmp_b[i] * tmp_c[i]);
          }
        }
    
        // 扩展行后，大炮种类变多，更新n
        n = a.size();
    
        // 下面就是01背包的解题思路了，这里使用了滚动数组，因此背包承重（即本题总火药量）要反向遍历
        int[] dp = new int[m + 1];
    
        for (int i = 0; i < n; i++) {
          for (int j = m; j >= b.get(i); j--) {
            dp[j] = Math.max(dp[j], dp[j - b.get(i)] + a.get(i));
          }
        }
    
        return dp[m];
      }
    }

#### Python算法源码 ####

朴素方法求解

# 输入获取
    n, m, t = map(int, input().split())
    guns = [list(map(int, input().split())) for _ in range(n)]
    
    
    # 算法入口
    def getResult():
        a = [0] * (n + 1)
        b = [0] * (n + 1)
        c = [0] * (n + 1)
    
        for i in range(1, n + 1):
            a[i] = guns[i - 1][0]  # a[i] 表示 第 i 种大炮的威力
            b[i] = guns[i - 1][1]  # b[i] 表示 第 i 种大炮每次攻击需要消耗的火药量
            c[i] = t // guns[i - 1][2]  # c[i] 表示 第 i 种大炮在规定时间t内，最多可以开几炮
    
        dp = [0] * (m + 1)
    
        # 遍历每种大炮
        for i in range(1, n + 1):
            # 总火药量
            for j in range(m, b[i] - 1, -1):
                # 大炮装填次数
                for k in range(1, c[i] + 1):
                    # 只有总火药量 j 足够，即 j >= b[i] * k,才能开火
                    if j >= b[i] * k:
                        # 遍历到大炮i，可以选，可以不选, 如果不选的话，则此时最大总威力保持不变, 如果选的话，则此时最大总威力 + a[i] * k，但是总火药量j减少b[i] * k
                        dp[j] = max(dp[j], dp[j - b[i] * k] + a[i] * k)
    
        return dp[m]
    
    
    # 算法调用
    print(getResult())

二进制优化求解

# 输入获取
    n, m, t = map(int, input().split())
    guns = [list(map(int, input().split())) for _ in range(n)]
    
    
    # 算法入口
    def getResult(n, m, t, guns):
        tmp_a = [0] * (n + 1)
        tmp_b = [0] * (n + 1)
        tmp_c = [0] * (n + 1)
    
        for i in range(1, n + 1):
            tmp_a[i] = guns[i - 1][0]  # a[i] 表示 第 i 种大炮的威力
            tmp_b[i] = guns[i - 1][1]  # b[i] 表示 第 i 种大炮每次攻击需要消耗的火药量
            tmp_c[i] = t // guns[i - 1][2]  # c[i] 表示 第 i 种大炮在规定时间t内，最多可以开几炮
    
        # tmp_a 使用二进制优化 扩展行后变为 a
        a = []
        # tmp_b 使用二进制优化 扩展行后变为b
        b = []
    
        # 使用二进制优化，扩展行
        x = 1
        while x <= n:
            # 注意这里 j 是二进制数，对应物品的件数，通过左移运算，得到1，2，4，8.。。这样的二进制数
            y = 1
            while y <= tmp_c[x]:
                # 将一种物品多件，变为一种物品一件，即：
                a.append(tmp_a[x] * y)  # 老大炮的威力 * 多件 = 新大炮种类的威力
                b.append(tmp_b[x] * y)  # 老大炮的火药消耗 * 多件 = 新大炮种类的火药消耗
                tmp_c[x] -= y  # 注意，老大炮的总件数 减少 j
                y <<= 1
    
            #  比如需要二进制数组合出1~1000范围任意数，则此时最后一个数489无法使用2^n表示，只能单独作为一个数存在
            if tmp_c[x] != 0:
                a.append(tmp_a[x] * tmp_c[x])
                b.append(tmp_b[x] * tmp_c[x])
    
            x += 1
    
        # 扩展行后，大炮种类变多，更新n
        n = len(a)
    
        # 下面就是01背包的解题思路了，这里使用了滚动数组，因此背包承重（即本题总火药量）要反向遍历
        dp = [0] * (m + 1)
        for i in range(n):
            for j in range(m, b[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - b[i]] + a[i])
    
        return dp[m]
    
    
    # 算法调用
    print(getResult(n, m, t, guns))

[- 01_01_-CSDN]: https://fcqian.blog.csdn.net/article/details/128307663
[- 01_-CSDN]: https://fcqian.blog.csdn.net/article/details/128903531