记录方案的基本步骤

1. 从后往前遍历
2. 如果该状态与前一个状态-k + value[i][k]相等，则说明第i家公司分配了k个
3. 记录该状态

for(int i=n;i>=1;i--)
    {
        for(int k=0;k<=j;k++)
        {
            if(f[i][j]==f[i-1][j-k]+value[i][k])

#include <iostream>

using namespace std;

int n,m;
const int N=20;
int f[N][N];
int value[N][N];
int way[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>value[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            //注意此处一个都不选的情况要单独列出来，不能在下面求，
            //不然会一直把一个都不选的情况与后面的情况作比较
            f[i][j]=f[i-1][j];
            for(int k=1;k<=j;k++)
            {         
                f[i][j]=max(f[i][j],f[i-1][j-k]+value[i][k]);
            }
        }
    }

    cout<<f[n][m]<<endl;
    int j=m;
    for(int i=n;i>=1;i--)
    {
        for(int k=0;k<=j;k++)
        {
            if(f[i][j]==f[i-1][j-k]+value[i][k])
            {
                j=j-k;
                way[i]=k;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<i<<" "<<way[i]<<endl;
    }
    return 0;
}

二刷，求具体方案问题，尽量不要用维度优化，容易出问题

#include <iostream>

using namespace std;

const int N=20;
int f[N][N],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=1;j<=m;j++)
        {
            f[i][j]=f[i-1][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;

    int cur_m=m;
    //cout<<f[m-2]<<endl;
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=cur_m;j++)
        {
            //说明f[cur_m]是由第i组的f[cur_m-j]更新来的
            if(f[i][cur_m]==f[i-1][cur_m-j]+w[i][j])
            {
                cur_m=cur_m-j;
                way[i]=j;
                //cout<<j<<endl;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<i<<" "<<way[i]<<endl;
    }

    return 0;
}

2023/11/28

分组背包问题， 求具体方案
// fij: 在前i个公司中选，分配j台机器的最大收益
// 在前i组背包中选，体积不超过j时的最大收益

背包问题求具体方案总结

1. 从后往前遍历, i=n -> 1
2. 遍历每组选哪个背包 (分组背包需要这步)
3. if(f[i][cur_m]==f[i-1][cur_m-j]+w[i][j]) 则说明状态i-1更新到状态i，选了第i个背包，则记录路径
4. 剩余体积要减去第i个背包的体积

    int cur_m=m;
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=cur_m;j++)
        {
            //说明f[cur_m]是由第i组的f[cur_m-j]更新来的
            if(f[i][cur_m]==f[i-1][cur_m-j]+w[i][j])
            {
                cur_m=cur_m-j;
                path[i]=j;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<i<<" "<<path[i]<<endl;
    }

#include <iostream>
#include <cstring>

using namespace std;

const int N=110;
int n,m;

// 分组背包, 每组只能取一种
int w[N][N], v[N][N];
// fij: 在前i个公司中选，分配j台机器的最大收益
// 在前i组背包中选，体积不超过j时的最大收益
int f[N][N];
int path[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
            v[i][j] = j;
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j] = f[i-1][j];
            // 遍历每组背包选哪个物品
            for(int k=1;k<=j;k++)
            {
                if(j >= v[i][k])
                {
                    f[i][j] = max(f[i][j], f[i-1][j-v[i][k]] + w[i][k]);
                }
            }

        }

    }

    int res = f[n][m];
    cout<<res<<endl;

    int cur_m=m;
    //cout<<f[m-2]<<endl;
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=cur_m;j++)
        {
            //说明f[cur_m]是由第i组的f[cur_m-j]更新来的
            if(f[i][cur_m]==f[i-1][cur_m-j]+w[i][j])
            {
                cur_m=cur_m-j;
                path[i]=j;
                //cout<<j<<endl;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<i<<" "<<path[i]<<endl;
    }


    return 0;
}