c++ 动态规划 装箱
时间: 2023-11-21 11:56:00 浏览: 34
以下是C++中使用动态规划解决装箱问题的例子:
```c++
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n, i, j;
int f[200000];
int w[35];
cin >> m >> n;
for (i = 1; i <= n; ++i) {
cin >> w[i];
}
for (i = 1; i <= n; ++i) {
for (j = m; j >= w[i]; --j) {
if (f[j] < f[j - w[i]] + w[i]) {
f[j] = f[j - w[i]] + w[i];
}
}
}
cout << m - f[m] << endl;
return 0;
}
```
这个例子中,我们使用动态规划来解决装箱问题。我们定义一个数组`f`,其中`f[i]`表示容量为`i`的箱子最多可以装多少重量。我们遍历每个物品,对于每个物品,我们从大到小遍历箱子容量,如果当前箱子容量大于等于该物品的重量,我们就判断剩余箱子容量是否大于0,如果是,我们就更新`f[j]`的值。