闫式dp分析

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 11, M = 16;

int n, m;
int w[N][M];
int f[N][M];
int way[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 = 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] << endl;

    int j = m;
    for (int i = n; i; i -- )
        for (int k = 0; k <= j; k ++ )
            if (f[i][j] == f[i - 1][j - k] + w[i][k])
            {
                way[i] = k;
                j -= k;
                break;
            }

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

    return 0;
}

作者：Global_zzz
链接：https://www.acwing.com/activity/content/code/content/601561/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

改进代码，记录转移路径，递归遍历

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxm = 16;
const int maxn = 11;

int dp[maxn][maxm], result[maxn][maxm], n, m, profit[maxn][maxm];
void output(int x, int y);

int main()
{
        while(scanf("%d %d", &n, &m) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        memset(profit, 0, sizeof(profit));
        memset(result, 0, sizeof(result));
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
                scanf("%d", &profit[i][j]);
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                for(int k = 0; k <= j; k++)
                {
                    int val = dp[i - 1][j - k] + profit[i][k];
                    if(dp[i][j] <= val) //如果val>= dp[i][j] 表示根据贪心的方式更新
                    {
                        dp[i][j] = val;
                        result[i][j] = k; // 记录选取数量
                    }
                }
            }
        }
        printf("%d\n", dp[n][m]);
        output(n, m);
    }
        return 0;
}

void output(int x, int y)
{
    if(x == 0)
        return;
    output(x - 1, y - result[x][y]);
    printf("%d %d\n", x, result[x][y]);
}

作者：Global_zzz
链接：https://www.acwing.com/activity/content/code/content/601561/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。