$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：只从前\ i\ 组物品中选第\ k\ 个物品，体积不超过\ j\ 的价值$
  $属性：\max$

• $2. 状态转移$
  $选择第\ i\ 组物品的第\ k\ 个物品：f[i][j]=\max\{f[i-1][j-v[i][k]]+w[i][k]\}\ (0\le k\le s[i])$

求具体方案可参考： 背包问题求具体方案

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 11, M = 16;

int n,m;
int w[N][M];
int f[N][M]; //只从前 i 组物品中选第 k 个物品，体积不超过 j 的最大价值
int ways[N];

int main()
{
    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=1;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]<<endl;

    //求具体方案
    for(int i=n,j=m;i;i--)
        for(int k=0;k<=j;k++)
            if(f[i][j]==f[i-1][j-k]+w[i][k])
            {
                ways[i]=k;
                j-=k;
                break;
            }

    for(int i=1;i<=n;i++) cout<<i<<' '<<ways[i]<<endl;

    return 0;
}