The maximization of submodular functions under various kinds of constraints is a central component of many combinatorial optimization problems, since submodular functions naturally cover the property of diminishing returns. This dissertation comprises four scientific articles in which we consider three different combinatorial optimization problems involving the maximization of submodular functions under knapsack or cardinality constraints. The first article considers the maximization of a submodular function defined on a weighted set of items under a knapsack constraint with unknown capacity. Assume that items are packed sequentially into the knapsack, and that an oracle reveals whether an item being attempted for packing fits into the currently packed knapsack. If an item fits, it is packed irrevocably; otherwise, either packing stops immediately (packing without discarding), or the item is removed, and packing continues (packing with discarding). Our main result concerns non-adaptive packing without discarding, under the assumption that the unknown knapsack capacity is greater than or equal to the weight of the heaviest item. Specifically, we present the first polynomial-time algorithm for computing a universal policy that, for any unknown capacity, performs at least as well as the classical greedy algorithm, studied by Wolsey (1982), for the same known capacity. In the second article, we study a game-theoretic variant of maximizing a submodular function under a cardinality constraint. In this variant, an initial solution to the classical problem is determined first. Subsequently, a predetermined number of elements of the ground set, possibly containing elements of the initial solution, are deleted. If any deleted elements were part of the initial solution, they are replaced by a set of at most equal cardinality. The objective is to maximize the value of the ultimate solution, with the deletion being maximally disadvantageous to it. We analyze several special cases of this problem and present polynomial-time algorithms for computing optimal or approximately optimal ultimate solutions. For the general case, we present a polynomial-time algorithm whose approximation guarantee depends on the curvature of the submodular objective function. The last two articles of this dissertation address the classic problem of maximizing a submodular function under a knapsack constraint. The first of these articles focuses on exact solvers: We present a branch-and-bound algorithm along with several acceleration techniques. We compare it against two solvers by Sakaue and Ishihata (2018), which currently achieve the strongest performance reported in the literature, as well as a branch-and-cut algorithm implemented using Gurobi that solves a binary linear reformulation of the submodular knapsack problem, demonstrating that our methods are highly successful. The last article considers variants of the classical greedy algorithm for submodular maximization under a knapsack constraint studied by Wolsey (1982). While the classical algorithm assumes access to an exact incremental oracle in every iteration, we generalize the known approximation results for this algorithm to the presence of only an $\alpha$-approximate oracle that returns in every iteration an item whose relative marginal gain approximates the maximum relative marginal gain by at least $\frac{1}{\alpha}$, with $\alpha \geq 1$ fixed. We also present an approximation result for a variant of the classical greedy algorithm that uses an approximate oracle only in the first iteration and an exact oracle thereafter.