优化以下代码:#include<stdio.h> #include<stdlib.h> int max(int a,int b){ return a>b?a:b; } int main() { int n,m,i,j; scanf("%d%d",&n,&m); int w[n],p[n],f[200000]={0}; for(i=0;i<n;i++) scanf("%d",&w[i]); for(i=0;i<n;i++) scanf("%d",&p[i]); for(i=0;i<n;i++){ for(j=m;j>=1;j--){ if(j>=w[i]) f[j]=max(f[j],f[j-w[i]]+p[i]); } } printf("%d",f[m]); return 0; }
时间: 2024-03-25 10:37:18 浏览: 40
下面是优化后的代码:
```
#include<stdio.h>
#include<stdlib.h>
int max(int a,int b){
return a>b?a:b;
}
int main() {
int n,m,i,j;
scanf("%d%d",&n,&m);
int *w = (int*)malloc(sizeof(int) * n);
int *p = (int*)malloc(sizeof(int) * n);
int *f = (int*)calloc(m+1, sizeof(int));
for(i=0;i<n;i++) scanf("%d",&w[i]);
for(i=0;i<n;i++) scanf("%d",&p[i]);
for(i=0;i<n;i++){
for(j=m;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+p[i]);
}
}
printf("%d",f[m]);
free(w);
free(p);
free(f);
return 0;
}
```
主要的优化有两点:
1. 使用动态内存分配。将 `w`, `p` 数组使用 `malloc` 动态分配内存,避免了在栈上开辟大块内存的风险,同时在使用完后及时释放内存。
2. 将 `f` 数组使用 `calloc` 进行初始化。`calloc` 会在分配内存时将内存全部初始化为 0,避免了手动对 `f` 数组进行初始化的麻烦。
另外,对于循环的顺序也进行了一些调整,将内层循环的循环变量 `j` 改为从 `m` 到 `w[i]`,可以避免一些无用的计算。
阅读全文