#include <iostream> using namespace std; #define BAGSIZE 70 int bags(int daoju[],int n){ int dp[BAGSIZE+1][n+1]; for(int j=0;j<=BAGSIZE;j++) //表格第一列,道具为0,放法为0 dp[j][0] = 0; for(int i=0;i<=n;i++) //表格第一行,空间为0,放法为1 dp[0][i] = 1; for(int i=1;i<=BAGSIZE;i++){ for(int j=1;j<=n;j++){ dp[i][j] = dp[i][j-1]; if(i-daoju[j]>=0) dp[i][j] += dp[i-daoju[j]][j-1]; } } for(int i=0;i<=BAGSIZE;i++){ for(int j=0;j<=n;j++) cout<<dp[i][j]<<' '; cout<<endl; } return dp[BAGSIZE][n]; } int main() { int n; cin>>n; int daoju[n+1]; daoju[0] = 0; for(int i=1;i<=n;i++) cin>>daoju[i]; cout<<bags(daoju,n); return 0; } 优化这段代码。
时间: 2024-04-13 20:28:20 浏览: 18
可以该代码进行以下优化:
1. 使用动态数组代替变量长度数组:将 `int daoju[n+1];` 改为 `vector<int> daoju(n+1);`,这样可以更方便地操作数组。
2. 简化空间复杂度:由于每次计算 dp[i][j] 时只需要用到前一行的数据 dp[i-daoju[j]][j-1] 和当前行的数据 dp[i][j-1],因此可以将 dp 优化为两行的滚动数组。同时,由于第一列的值都是固定的,可以省略对第一列的计算。
3. 优化内层循环:在计算 dp[i][j] 的时候,可以将 `dp[i-daoju[j]][j-1]` 的计算结果保存下来,避免重复计算。
下面是优化后的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
#define BAGSIZE 70
int bags(const vector<int>& daoju, int n) {
vector<int> dp(BAGSIZE + 1);
dp[0] = 1;
for (int j = 1; j <= n; j++) {
for (int i = BAGSIZE; i >= daoju[j]; i--) {
dp[i] += dp[i - daoju[j]];
}
}
return dp[BAGSIZE];
}
int main() {
int n;
cin >> n;
vector<int> daoju(n + 1);
daoju[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> daoju[i];
}
cout << bags(daoju, n);
return 0;
}
```
通过以上优化,可以提高代码的执行效率和空间利用率。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)