#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct thing{ int val;//价值 int vol;//重量 }thing; int N, V; thing things[1011]; int dp[1011][1011]; int ans() { int num[1011] = {0}; memset(dp, 0, sizeof(dp)); for(int i = 1; i <= N; i++) { int d = 0; for(int j = 1; j <= V; j++) { if(things[i].vol > j) { dp[i][j] = dp[i-1][j];//不放 } else { dp[i][j] = max(dp[i-1][j], dp[i-1][j-things[i].vol] + things[i].val);//放入 改变 } if(d == dp[i][j]) { num[i] = 0; } else { num[i] = 1; d += dp[i][j]; } } } for(int i = 1;i <=N;i++) { printf("%d",num[i]); } printf("\n"); return dp[N][V]; } int max(int a,int b) { if(a>b) return a; else return b; } int main() { int num[1011] = {0}; scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%d", &things[i].vol); } for(int j = 1; j <= N; j++) { scanf("%d", &things[j].val); } scanf("%d",&V); printf("%d\n", ans()); return 0; }优化这段代码
时间: 2024-02-14 11:13:15 浏览: 80
C代码教程1显示#include <stdio.
这段代码是一个背包问题的动态规划解法,存在以下几个可以优化的地方:
1. 对于一个物品,只需要在遍历到它时考虑是否放入背包,不需要遍历所有容量。
2. 可以使用滚动数组将二维的 dp 数组压缩为一维,降低空间复杂度。
3. 可以使用 scanf 的格式化字符串 "%d %d" 一次读入两个整数,避免多次调用 scanf。
4. 可以将 max 函数改为一个内联函数,在编译时直接将其替换为比较操作,提高效率。
优化后的代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct thing{
int val; // 价值
int vol; // 重量
} thing;
int N, V;
thing things[1011];
int dp[1011];
inline int max(int a, int b) {
return a > b ? a : b;
}
int ans() {
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= N; i++) {
for(int j = V; j >= things[i].vol; j--) {
dp[j] = max(dp[j], dp[j-things[i].vol] + things[i].val);
}
}
return dp[V];
}
int main() {
scanf("%d", &N);
for(int i = 1; i <= N; i++) {
scanf("%d %d", &things[i].vol, &things[i].val);
}
scanf("%d", &V);
printf("%d\n", ans());
return 0;
}
```
阅读全文