Knapsack CodeForces

可以将大量同种物品合并为$lcm$来优化, 复杂度$O(nlcm^2)$, 好像可以用bitset优化到$O(nlcm^2/omega)$, 但是没看太懂

const int L = 840, M = L*8;
ll w;
ll dp[10][M];

void chkmax(ll &x,ll y) {x=max(x,y);}

int main() {
	scanf("%lld", &w);
	memset(dp, -1, sizeof dp);
	dp[0][0] = 0;
	REP(i,1,8) {
		ll cnt;
		scanf("%lld", &cnt);
		REP(j,0,M) if (dp[i-1][j]!=-1) {
			int mx = min(cnt, (ll)L/i);
			REP(k,0,mx) {
				chkmax(dp[i][j+k*i],dp[i-1][j]+(cnt-k)/(L/i));
			}
		}
	}
	ll ans = 0;
	int mx = min((ll)M,w);
	REP(i,0,mx) if (dp[8][i]!=-1) {
		ans = max(ans, i+L*min(dp[8][i],(w-i)/L));
	}
	printf("%lld
", ans);
}