126 lines
4.7 KiB
C++
126 lines
4.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
int main()
|
||
{
|
||
double count1 = 0; // 查表次数
|
||
double sum_time1 = 0; // 总耗时
|
||
double count2 = 0; // 查表次数
|
||
double sum_time2 = 0; // 总耗时
|
||
double count3 = 0; // 查表次数
|
||
double sum_time3 = 0; // 总耗时
|
||
|
||
int n = 500; // 物品数量
|
||
int repeat = 50; // 重复实验的次数
|
||
srand(time(0));
|
||
for (int m = 0; m < repeat; m++)
|
||
{
|
||
vector<int> val(n);
|
||
for (int j = 0; j < n; j++)
|
||
{
|
||
val[j] = rand() % 20 + 1; // 不能为0
|
||
}
|
||
|
||
vector<int> wt(n);
|
||
for (int j = 0; j < n; j++)
|
||
{
|
||
wt[j] = rand() % 20 + 1; // 不能为0
|
||
}
|
||
|
||
int W = 1000; // 背包总容量
|
||
|
||
// 二维带循环
|
||
clock_t start_time1, end_time1;
|
||
start_time1 = clock(); // 开始记时
|
||
vector<vector<int>> dp1(n + 1, vector<int>(W + 1, 0));
|
||
for (int i = 1; i <= n; ++i)
|
||
{
|
||
for (int w = 1; w <= W; ++w)
|
||
{
|
||
for (int k = 0; k <= w / wt[i - 1]; ++k)
|
||
{
|
||
dp1[i][w] = max(dp1[i][w], dp1[i - 1][w - k * wt[i - 1]] + k * val[i - 1]);
|
||
count1 += 2;
|
||
}
|
||
}
|
||
}
|
||
end_time1 = clock(); // 结束计时
|
||
sum_time1 += (double)(end_time1 - start_time1) / CLOCKS_PER_SEC;
|
||
int anwser1 = dp1[n][W];
|
||
// cout << anwser1 << ' ' << count1 << endl; //验证结果是否正确
|
||
|
||
// 二维不带循环
|
||
clock_t start_time2, end_time2;
|
||
start_time2 = clock(); // 开始记时
|
||
vector<vector<int>> dp2(n + 1, vector<int>(W + 1, 0)); // 记录情况的二维数组
|
||
for (int i = 1; i <= n; ++i) // 遍历物品
|
||
{
|
||
for (int w = 1; w <= W; ++w) // 遍历容量
|
||
{
|
||
if (wt[i - 1] <= w)
|
||
{
|
||
dp2[i][w] = max(dp2[i - 1][w], dp2[i][w - wt[i - 1]] + val[i - 1]);
|
||
count2 += 2;
|
||
}
|
||
else
|
||
{
|
||
dp2[i][w] = dp2[i - 1][w];
|
||
count2++;
|
||
}
|
||
}
|
||
}
|
||
end_time2 = clock(); // 结束计时
|
||
sum_time2 += (double)(end_time2 - start_time2) / CLOCKS_PER_SEC;
|
||
int anwser2 = dp2[n][W];
|
||
// cout << anwser2 << ' ' << count2 << endl; //验证结果是否正确
|
||
|
||
// 一维数组优化
|
||
clock_t start_time3, end_time3;
|
||
start_time3 = clock(); // 开始记时
|
||
vector<int> dp3(W + 1, 0); // 使用一维数组进行动态规划
|
||
|
||
for (int i = 0; i < n; ++i) // 遍历物品
|
||
{
|
||
for (int w = wt[i]; w <= W; ++w) // 遍历单个重量
|
||
{
|
||
dp3[w] = max(dp3[w], dp3[w - wt[i]] + val[i]);
|
||
count3 += 2;
|
||
}
|
||
}
|
||
end_time3 = clock(); // 结束计时
|
||
sum_time3 += (double)(end_time3 - start_time3) / CLOCKS_PER_SEC;
|
||
int anwser3 = dp3[W];
|
||
// cout << anwser3 << ' ' << count3 << endl; //验证结果是否正确
|
||
}
|
||
|
||
cout << endl;
|
||
cout << "————————二维数组带循环的推导式————————" << endl;
|
||
cout << "递推公式为：dp[i][j] = max(dp[i][j], dp[i-1][j-k*wt[i]] + k*val[i]) k>=0&&k<=(W/wt[i])" << endl;
|
||
cout << "实验次数：" << repeat << "次" << endl;
|
||
cout << "物品种类：" << n << endl;
|
||
cout << "背包容量：1000" << endl;
|
||
cout << "平均时间：" << sum_time1 / repeat << "秒" << endl;
|
||
cout << "平均查表：" << count1 / repeat << "次" << endl;
|
||
|
||
cout << endl;
|
||
cout << "————————二维数组不带循环的推导式————————" << endl;
|
||
cout << "递推公式为：dp[i][j] = max(dp[i-1][j], dp[i][j-wt[i]] + val[i])" << endl;
|
||
cout << "实验次数：" << repeat << "次" << endl;
|
||
cout << "物品种类：" << n << endl;
|
||
cout << "背包容量：1000" << endl;
|
||
cout << "平均时间：" << sum_time2 / repeat << "秒" << endl;
|
||
cout << "平均查表：" << count2 / repeat << "次" << endl;
|
||
|
||
cout << endl;
|
||
cout << "————————一维数组优化————————" << endl;
|
||
cout << "递推公式为：dp[j] = max(dp[j], dp[j-w[i]] + v[i])" << endl;
|
||
cout << "实验次数：" << repeat << "次" << endl;
|
||
cout << "物品种类：" << n << endl;
|
||
cout << "背包容量：1000" << endl;
|
||
cout << "平均时间：" << sum_time3 / repeat << "秒" << endl;
|
||
cout << "平均查表：" << count3 / repeat << "次" << endl;
|
||
|
||
return 0;
|
||
}
|