C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[20][20];
int V[20][20],W[20][20];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> W[i][j];
        }
    }
    for(int i = 1; i <= n; i++){ //第几个公司
        for(int j = m; j >= 0; j--){ //对于每个公司求01背包，最多求m个机器时的利润。
            dp[i][j] = dp[i-1][j];
            for(int k = 0; k <= m; k++){//该公司拥有k个机器所获得的利润
                if(j>=k)
                    dp[i][j] = max(dp[i][j],dp[i-1][j-k]+W[i][k]);
            }
        }
    }
    int tol = m;
    vector<int> c;
    cout << dp[n][m] << endl;
    //将结果逆向，
    for(int i = n; i >= 1; i--){
        for(int k = 0; k <= m; k++){ //求每个公司是否可以采取k个机器来使总利润最大，即总利润是否可以由当前公司拥有k个机器时转移到。
            if(dp[i][tol] == dp[i-1][tol-k]+W[i][k]){
                c.push_back(k);
                tol -= k;
                break;
            }

        }
    }
    for(int i = c.size()-1,j = 1; i >= 0; j++,i--){
        cout << j << " " << c[i] << endl;
    }
    return 0;
}