大模型训练显存优化算法

📝 题目描述

难度： 🟡 中等
标签： 动态规划 0/1背包

题目太长，无关内容很多，直接看输入输出示例即可。
输入描述：

输出描述：

示例1：
输入：
10
5
3 4 5 6 7
1 2 3 5 5
2 3 4 5 6
输出：
6

解释：

� 解题思路

从题目中可以知道，目的是凑齐需要的存储空间，并且要求代价最小。
对于有条件限制的题目，可以尝试使用动态规划方法，本题可以把需要的存储空间m看成背包容量m，代价p看做物品价值p，候选张量看做物品，候选张量每种最多选一次，为0/1背包问题，且候选张量内存可以超过需要的存储空间，即物品的重量可以超过背包容量，为无限背包变种。
由于每个物品都可以选择swap或者重计算，直接选择代价小的作为物品的重量。
第一步，确定dp 含义，
 首选二维dp，因为思路清晰简单。令纵轴为物品（候选张量），横轴为背包大小（需要的空间），dp代表价值（代价）
第二步，确定递推公式，
 在当前步都有两种情况，
  当前背包容量小于当前物品重量（但是没有超过需求容量m），直接继承dp[i-1][j]即可
  反之，可以选则当前物品或者不选择，取较小的一个即可min（dp[i-1][j],dp[i-1][j-mem[i]]+p[i]）
 特别的，对于无限背包，当前背包容量为m时，需要拿出讨论，这时可以选择的方案为：
dp[i-1][j-mem[i]]到dp[i-1][m]，选择其中代价最小的即可，因为在这个区间内，放置候选物品i都可以满足条件
第三步，确定边界条件，这个是求最小值，一般全部初始化为+INF，即一个很大的数字，再把dp[0]
[0]初始化为0
第四步，遍历顺序，按照步骤三的递推公式按行遍历即可
第五步，确定结果，dp行尾的会存储最小的符合条件的值，因此输出二维表最右下角的值即可。注意，本题可能有无解的情况，那么需要对结果检查，是否不为+INF，否则输出error

� 代码实现

#include<bits/stdc++.h>
using namespace std;

int main(){

    // dp dp是价值，i是所有可选的方案，j是0-m，表示容量，无限背包
    // 状态转移，判断当前的容量大小先看当前的容量是否为m，为m则取min（dp[i-1][m-w[i]]+v[i]~dp[i-1][m]+v[i]）
    // 否则就取min(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
    int m,n;
    cin>>m>>n;
    vector<int>mem(n,0);
    vector<int>p(n,0);
    int cnt=0;
    int temp=0;
    while(cnt<n){
        cin>>temp;
        mem[cnt]=temp;
        cnt++;
    }
    cnt=0;
    while(cin>>temp){
        if(cnt<n){
            p[cnt]=temp;
        }
        else{
            p[cnt%n]=min(temp,p[cnt%n]);
        }
        cnt++;
    }
    vector<vector<int>>dp(n+1,vector<int>(m+1,1e9));
    dp[0][0]=0;
    // 开始画表
    for(int i=1;i<n+1;i++){
        for(int j=0;j<m+1;j++){
            if(j<mem[i-1]){
                dp[i][j]=dp[i-1][j];
            }
            else if(j>=mem[i-1]){
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-mem[i-1]]+p[i-1]);
            }
            if(j==m){
                for(int k=max(m-mem[i-1],0);k<m+1;k++){
                    dp[i][m]=min(dp[i][m],dp[i-1][k]+p[i-1]);
                }
            }
        }
    }
    dp[n][m]==1e9?cout<<"error":cout<<dp[n][m];
    return 0;
}

📊 复杂度分析

检查每行最后一个假设平均需要k次，时间复杂度为：

• 时间复杂度： O(mnk)
• 空间复杂度： O(mn)

日期： 2026-4-9