山山的投资 c++

Question

山山最近在考虑一个五年投资计划。现在有T(1 <= T <= 10) 家投资公司，每一家都经营n(1 <= n <= 1000)种理财产品，并给出了每一种产品目前的价值ai以及五年后的价值bi(1 <= ai, bi<= 1000)。山山可以从这T家投资公司中选取若干家，并在其中投入一定数量的钱。对于一家投资公司，山山可以购买其中的理财产品，同一公司的每一种产品最多购买一次。五年后山山会将所有的产品全部卖出。
当山山选择一家投资公司时，需要缴纳ki(1 <= ki<=1000)的手续费。注意若山山选择了这一家公司，即使山山不购买任何该公司的理财产品，仍然要缴纳手续费。
现在山山手中金币数为m(1 <= m <= 1000)，你需要设计一种方案使得山山能够在五年后获得最大数量的金币。

输入格式:

 第一行三个正整数T, n, m，分别表示投资公司数量，每家公司提供理财产品数量，以及山山现在的金币数。 




 下面一行，包含T个整数ki，表示第i家投资公司的手续费。 




 接下来T行，每行n个数ai，表示现在每一家公司第i个投资产品的价格。 




 之后T行，每行n个数bi，表示五年后每一家公司第i个投资产品的价格。 

输出格式:

输出一行一个整数，表示山山五年后持有的最大金币数。
限制:

空间限制：128MByte
时间限制：1秒
样例:

输入：

2 2 10
1 1
2 3
1 4
1 4
1 6
输出：

11
提示:

山山可以选择两家公司，缴纳2手续费，剩余8金币。山山用3金币购买第一家公司的第二种产品，并用4金币购买第二家公司的第二种产品，剩余1金币。五年后得到4+6金币，共计11金币，为最大值。

Answer 1

参考GPT和自己的思路：

这道题可以使用 01 背包的思路求解。假设 dp[i][j] 表示只考虑前 i 家投资公司，花费不超过 j，能够获得的最大金币数。那么有以下状态转移方程：

当不选择第 i 家公司时：dp[i][j] = dp[i-1][j]

当选择第 i 家公司时：dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i][k]] + value[i][k])

其中，cost[i][k] 表示第 i 家公司的第 k 种产品的手续费，value[i][k] 表示第 i 家公司的第 k 种产品五年后能够获得的金币数。

最终的答案是 dp[T][m]，即 T 家投资公司中，花费不超过 m 时所能获取到的最大金币数。

需要注意的是，在输入阶段，需要同时记录 ai 和 bi 两个数组，这个过程比较麻烦，需要做好数组下标的映射。另外，本题的时间和空间限制都比较友好，就算使用暴力的 01 背包，也可以 AC 本题。