洛谷:P5662
OJ : P4964
t
、纪念品种类 n
以及初始的金币数量 m
。然后读取每种纪念品在每天的价格。f[j]
表示用 j
枚金币能获得的最大利润。我们采用完全背包的方式进行遍历,从小到大更新金币数 j
。f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k])
,表示若当前持有金币数 j
,若购买第 i
种纪念品并在下一天卖出,能否获得更大的利润。f[m]
加到现有金币数 m
上,作为下一天的初始金币数,继续进行接下来的买卖操作。t-1
天交易后的最大金币数。该算法本质上是一个基于完全背包的动态规划问题,通过每天进行背包转移,计算在未来的买卖中所能获得的最大利润。
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include <iostream> #include <memory.h> // 包含 memset 函数头文件 using namespace std; const int N = 101; // 最大纪念品种类数 const int M = 10001; // 最大金币数量 int n, m, t; // n: 纪念品种类, m: 初始金币数量, t: 天数 int price[N][N], f[M]; // price[i][j] 表示第 j 天第 i 种纪念品的价格, f[j] 表示用 j 枚金币可以获得的最大盈利 int main(){ freopen("souvenir.in","r",stdin); freopen("souvenir.out","w",stdout); // 读取输入的天数 t、纪念品种类 n 和初始金币数量 m cin >> t >> n >> m; // 读取每种纪念品在每一天的价格,注意这里的 i 表示天数,j 表示纪念品种类 for(int i = 1; i <= t; i++) for(int j = 1; j <= n; j++) cin >> price[j][i]; // price[j][i] 表示第 i 天第 j 种纪念品的价格 // 循环从第 1 天到第 t-1 天,处理买卖操作 for(int k = 1; k < t; k++) { // 每一轮交易前都需要将动态规划数组 f 置零,表示当前没有盈利 memset(f, 0, sizeof f); // 遍历每种纪念品 for(int i = 1; i <= n; i++) { // 完全背包的思想:正序遍历金币数 j,从商品价格开始,尝试用 j 枚金币进行交易 // 这里表示从金币数 price[i][k] 开始,直到最大金币数 m for(int j = price[i][k]; j <= m; j++) { // 状态转移方程:f[j] 表示用 j 枚金币所能获得的最大盈利 // f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]) // 意思是如果用 j 枚金币买入第 i 种纪念品,再在第 k+1 天卖出,计算出能否获得更大的盈利 f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]); } } // 在每一轮结束时,m 需要加上 f[m],即这一天买卖操作获得的最大盈利,进入下一轮 m += f[m]; } // 最终输出金币数量,即经过 t-1 天后的最大金币数量 cout << m; return 0; } |