1 01背包，一维

 cin>>n>>m; 物品个数，容量
    while(n--)
    {
            cin>>v>>w; 每个物品的体积 价值
            for(int j=m;j>=v;j--)
            {
                f[j]=max(f[j],f[j-v]+w);
            }
    }
    cout<<f[m];

2 完全背包

    cin>>n>>m;
    while(n--)
    {
        cin>>v>>w;
        for(int j=1;j<=m;j++)
        {
            f[j]=f[j];
            if(j>=v) f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<f[m];

3 二维背包

cin>>n>>V>>M;
     for (int i = 0; i < n; i ++ )
    {
        int v, m, w;//体积 重量 价值 
        cin >> v >> m >> w;
        //01背包，体积，重量从大到小循环（优化） 
        for (int j = V; j >= v; j -- )
            for (int k = M; k >= m; k -- )
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }

    cout << f[V][M] << endl;

4二维，完全，输出方案背包 容量必须等于，不是≤

int f[21][N][N];
int main()
{
    cin >> n >> k >> p;
    memset(f, -0x3f, sizeof f);
    f[0][0][0] = 0;
    int m;
    for (m = 1; ;m ++ )//1~20的数
    {
        int v = power(m, p);//当前乘积v（背包容量169）
        if (v > n) break;//


        for (int i = 0; i <= n; i ++ )//因子幂次和169
            for (int j = 0; j <= k; j ++ )//k个数
            {
                f[m][i][j] = f[m - 1][i][j];//不选数m

                if (i >= v && j)// 和不到i，且还有位置，才选m
                f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);
            }
    }
    m -- ;//break时，m已经超过了，需要减1
    if (f[m][n][k] < 0) puts("Impossible");
    else
    {
        printf("%d = ", n);
        bool is_first = true;//特判第一项，前面不用输出“+”
        while (m)
        {
            int v = power(m, p);
//!第m个物品，可以选m次，这里要循环到不能选m为止
            while (n >= v && k && f[m][n - v][k - 1] + m == f[m][n][k])
            //选m，说明f[m][n][k]在max（f[m-1][n][k],f[m][n - v][k - 1] + m）时，等于后者
            {
                if (is_first) is_first = false;
                else printf(" + ");
                printf("%d^%d", m, p);
                n -= v, k --;//回溯路径，要更新限制值，不然一直循环
            }
            m -- ;
        }
    }
    return 0;
}