背包问题($O(tnm)$)

• 先枚举每天，然后依次枚举每种物品，因为可以无限次交易，所以是完全背包

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=10100;
int w[N][N];
int f[M]; //f[k]表示在金币不超过k的时候的最大利润
int main()
{
    int t,n,m;
    cin>>t>>n>>m;
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j];
    int res=0;
    for(int i=1;i<t;i++) //枚举第i天到第i+1天的利润
    {
        memset(f,0,sizeof f); //清空
        for(int j=1;j<=n;j++) //枚举每个物品
                for(int k=w[i][j];k<=m;k++) //完全背包体积从小到大
                    f[k]=max(f[k],f[k-w[i][j]]+w[i+1][j]-w[i][j]); //更新价值
        m+=f[m];//更新金币数目
    }
    cout<<m;
    return 0;
}