抽大象事件
查看原帖
抽大象事件
725807
lizeyuannb楼主2024/5/23 19:42
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]);
		}
	}

关于```cpp if(i < 2) continue; if(i < 3) continue;

这两行代码,删了之后正确,不删60分,为什么呢?
是因为空间优化后f[j]的含义变化,不再是前i个物品体积为j的最优解了吗?
2024/5/23 19:42
加载中...