最小重量机器问题 设某一机器由 n 个部件组成,每种部件都可以从 m 个不同的供应商处购得。设 Wij 是从供应商 j 处购得的部件 i 的重量,Cij 是相应的价格。试设计一个算法,给出总价格不超过 c 的最小重量机器设计C++编程实现
时间: 2024-02-12 17:08:51 浏览: 40
以下是该问题的C++代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, c;
int W[105][105], C[105][105];
int dp[105][10005];
int main() {
cin >> n >> m >> c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> W[i][j] >> C[i][j];
}
}
memset(dp, INF, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= c; j++) {
for (int k = 1; k <= m; k++) {
if (C[i][k] <= j) {
dp[i][j] = min(dp[i][j], dp[i-1][j-C[i][k]] + W[i][k]);
}
}
}
}
int ans = 0;
for (int j = c; j >= 0; j--) {
if (dp[n][j] <= c) {
ans = dp[n][j];
break;
}
}
cout << ans << endl;
return 0;
}
```
该算法采用三重循环实现状态转移。时间复杂度为 O(nmc),空间复杂度为 O(nc)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c++](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)