C++代码完成以下编程任务:使用动态规划法实现0-1背包问题的求解,测试数据随机生成,相同程序重复执行 100 次以测试效率
时间: 2024-03-15 11:47:19 浏览: 42
c++实现动态规划算法解决0-1背包问题
5星 · 资源好评率100%
以下是使用动态规划法实现0-1背包问题的C++代码,其中测试数据随机生成,相同程序重复执行100次以测试效率:
```c++
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
int max(int a, int b) {
return (a > b) ? a : b;
}
int knapsack(int W, vector<int> wt, vector<int> val, int n) {
vector<vector<int>> K(n + 1, vector<int>(W + 1));
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
}
else if (wt[i - 1] <= w) {
K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
}
else {
K[i][w] = K[i - 1][w];
}
}
}
return K[n][W];
}
int main() {
srand((unsigned)time(NULL));
int W = rand() % 100 + 1; // 背包容量
int n = rand() % 20 + 1; // 物品个数
vector<int> wt(n); // 物品重量
vector<int> val(n); // 物品价值
// 随机生成物品重量和价值
for (int i = 0; i < n; i++) {
wt[i] = rand() % 50 + 1;
val[i] = rand() % 100 + 1;
}
int max_val = knapsack(W, wt, val, n); // 求解最大价值
cout << "背包容量:" << W << endl;
cout << "物品个数:" << n << endl;
cout << "物品重量:" << endl;
for (int i = 0; i < n; i++) {
cout << wt[i] << " ";
}
cout << endl;
cout << "物品价值:" << endl;
for (int i = 0; i < n; i++) {
cout << val[i] << " ";
}
cout << endl;
cout << "最大价值:" << max_val << endl;
// 重复执行100次,测试效率
clock_t start, end;
double cpu_time_used;
start = clock();
for (int i = 0; i < 100; i++) {
knapsack(W, wt, val, n);
}
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
cout << "程序运行时间:" << cpu_time_used << "秒" << endl;
return 0;
}
```
在程序中,我们随机生成了背包容量、物品个数、物品重量和价值,然后调用 `knapsack` 函数来求解最大价值,并重复执行100次来测试效率。
阅读全文