2019年CSP-J纪念品（洛谷P5662）：完全背包实战

一、问题背景与算法选择

2019年CSP-J组纪念品问题考察了动态规划中的完全背包应用。题目要求我们在T天内通过买卖N种纪念品使初始资金M最大化，每天可以无限次买卖纪念品。解题关键在于将每天的交易视为独立的完全背包问题。

二、完整代码解析（含详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T, N, M;
    cin >> T >> N >> M;
    
    vector<vector<int>> prices(T, vector<int>(N));
    for (int i = 0; i < T; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> prices[i][j];
        }
    }
    
    // 每天处理时，计算当天到第二天的最大收益
    for (int day = 0; day < T - 1; ++day) {
        vector<int> DP(M + 1, 0); // dp[i]表示i金币能获得的最大收益
        
        for (int item = 0; item < N; ++item) {
            int cost = prices[day][item];
            int profit = prices[day + 1][item] - cost;
            
            if (profit <= 0) continue; // 无利可图则跳过
            
            // 完全背包问题解法
            for (int j = cost; j <= M; ++j) {
                dp[j] = max(dp[j], dp[j - cost] + profit);
            }
        }
        
        // 更新最大金币数
        M += dp[M];
    }
    
    cout << M << endl;
    return 0;
}

三、关键算法解析

1. 完全背包模型：将每种纪念品视为可以无限取的物品，利润为价值，买入价为重量

2. 滚动更新策略：每天独立计算最优交易组合，累计收益到总资金

3. 剪枝优化：跳过利润非正的交易机会（profit <= 0）