思路

一个分组背包问题，只不过这里还要求记录路径，记录路径的话只要找到每一个点取了什么就行了，熟悉分组背包的很快就写出来了。

步骤：
1.用way数组存下路径，用f[i][j]表示扫描到第i个背包的时候容量有j的解
2.开始dp ：

第一层循环：枚举背包，从前往后扫描
第二层循环：枚举容量，一定要先枚举容量，不然会漏情况，解也就不对了
第三层循环：枚举每一个背包取了多少个

3.开始找路径，由于我们知道f[n][m]就是解，那么我们就从f[n][m]开始往前找

先用j来表示当前的容量，初始值为m（因为我们从前往后找）
第一层循环：从n个背包开始往前扫描
第二层循环：枚举从第i个背包里取了多少个，0<=k<=j，判断：如果从第i个背包里去了k个物品的值和当前解相同就证明路径中从第i个背包中取了k个，所以，记录下k的值，并且更新容量，也就是j - =k.

4.输出

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int  N=30;
int f[N][N];
int w[N][N];
int way[N];
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=0;j<=m;j++){
            for(int k=0;k<=j;k++){
                f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
            }
        }
    }
    cout << f[n][m] << "\n";
    int j=m;
    for(int i=n;i>0;i--){
        for(int k=0;k<=j;k++){
            if(f[i][j]==f[i-1][j-k]+w[i][k]){
                j-=k;
                way[i]=k;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout << i << " " <<way[i] << "\n";
    }
}