通过软盘拷贝文件
#动态规划 2025-03-31 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <ostream>
#include <sstream>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

constexpr int STORAGE_MAX = 1474560;
constexpr int BYTE = 512;

int main() {

	int n;
	cin >> n;

	vector<int> data(n);
	for (int i = 0; i < n; i++) {
		cin >> data[i];
	}

	// 确定背包容量
	int capacity = STORAGE_MAX / BYTE;
	// 确定物品及其价值表
	vector<int> weight(n, 0);
	for (int i = 0; i < n; ++i) {
		weight[i] = ceil(data[i] / 512.0);	// 关键步骤
	}

	vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
	for (int i = 1; i <= n; ++i) {    // 物品
		for (int j = 1; j <= capacity; ++j) {    // 容量
			if (j < weight[i - 1]) {
				dp[i][j] = dp[i - 1][j];
			} else {
				dp[i][j] = max(dp[i - 1][j], dp[i-1][j - weight[i - 1]] + data[i - 1]);
			}
		}
	}

	cout << dp[n][capacity] << endl;

	return 0;
}

这里面有个步骤很关键，即求价值表的时候：

1
weight[i] = ceil(data[i] / 512.0);

ceil 是向上取整，floor 是向下取整，因此接受的参数都是 浮点数。

3.5 向上取整为 4，3.5 向下取整 3。