抽大象事件

lizeyuannb @ 2024-05-23 19:42:30

for(int i = 1; i <= m; i ++) {
        if(!zhup[i]) continue;
        for(int k = n; k >= zhup[i]; k --) {
            f[k] = max(f[k], f[k-zhup[i]] + zhuv[i]);
            if(k >= zhup[i] + fup[i][1])
                f[k] = max(f[k], f[k-zhup[i]-fup[i][1]] + zhuv[i] + fuv[i][1]);
            if(k >= zhup[i] + fup[i][2])
                f[k] = max(f[k], f[k-zhup[i]-fup[i][2]] + zhuv[i] + fuv[i][2]);
            if(k >= zhup[i] + fup[i][1] + fup[i][2])
                f[k] = max(f[k], f[k-zhup[i]-fup[i][1]-fup[i][2]] + zhuv[i] + fuv[i][1] + fuv[i][2]);
        }
    }

这两行代码，删了之后正确，不删60分，为什么呢？
是因为空间优化后f[j]的含义变化，不再是前i个物品体积为j的最优解了吗？

by lry0404 @ 2024-05-25 14:02:02

#include <iostream>
using namespace std;
int n, m, v[65], p[65], q[65], c1[65], c2[65], gv[65][4], gw[65][4], f[32005];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> v[i] >> p[i] >> q[i];
        if (q[i])
            if (c1[q[i]])
                c2[q[i]] = i;
            else
                c1[q[i]] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        if(q[i] == 0)
        {
            for(int j = 0; j <= 1; j++)
            {
                for(int k = 0; k <= 1; k++)
                {
                    gv[i][j * 2 + k] = j * v[c1[i]] + k * v[c2[i]] + v[i];
                    gw[i][j * 2 + k] = j * v[c1[i]] * p[c1[i]] + k * v[c2[i]] * p[c2[i]] + v[i] * p[i];
                }
            }
        }
    }
    for(int i = 1; i <= m; i++)
    {
        if(q[i] == 0)
        {
            for(int j = n; j >= 0; j--)
            {
                for(int k = 0; k < 4; k++)
                {
                    if(j >= gv[i][k])
                    {
                        f[j] = max(f[j], f[j - gv[i][k]] + gw[i][k]);
                    }
                }
            }
        }
    }
    cout << f[n] << endl;
    return 0;
}