优化这段代码 减小算法复杂度#include <iostream> using namespace std; int c,n; int v[1000],w[1000]; int x[1000],m[1000][1000]; void Knapsack(int v[],int w[],int c,int n) { int jmax=min(w[n]-1,c); for(int j=0;j<=jmax;j++) m[n][j]=0;//初始化 for(int j=w[n];j<=c;j++) m[n][j]=v[n];//初始化 for(int i=n-1;i>1;i--) { jmax=min(w[i]-1,c); for(int j=0;j<=jmax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } void Traceback(int w[],int c,int n,int x[]) { for(int i=1;i<n;i++) { if(m[i][c]==m[i+1][c]) x[i]=0; else { x[i]=1; c-=w[i]; } } x[n]=m[n][c]?1:0; } int main() { cin>>c>>n; for(int i=1;i<=n;i++) cin>>v[i]; for(int i=1;i<=n;i++) cin>>w[i]; Knapsack(v,w,c,n); Traceback(w,c,n,x); cout<<m[1][c]<<endl; for(int i=1;i<=n;i++) if(x[i]==1) cout<<i<<" "; cout<<endl; return 0; } 输入样例： 10 5 6 3 5 4 6 2 2 6 5 4 输出样例： 15 1 2 5

这段代码使用了动态规划算法求解 0/1 背包问题。以下是对代码的优化：

1. 使用滚动数组优化空间复杂度：

将动态规划中的二维数组 m[i][j] 压缩到一维数组 m[j] 中，同时，由于状态转移方程只与 i+1 相关，因此可以使用滚动数组的方式，只保存上一层的值。

2. 代码风格优化：

规范代码的缩进和命名，使其更易读懂。

优化后的代码如下：

#include <iostream>
using namespace std;

const int MAXN = 1000;
int c, n;
int v[MAXN], w[MAXN];
int x[MAXN], m[MAXN];

void Knapsack(int v[], int w[], int c, int n) {
    for (int j = 0; j <= c; j++) {
        m[j] = 0;
    }
    for (int i = n - 1; i >= 1; i--) {
        for (int j = c; j >= w[i]; j--) {
            m[j] = max(m[j], m[j - w[i]] + v[i]);
        }
    }
}

void Traceback(int w[], int c, int n, int x[]) {
    for (int i = 1; i < n; i++) {
        if (m[c] == m[c - w[i]] + v[i]) {
            x[i] = 1;
            c -= w[i];
        }
        else {
            x[i] = 0;
        }
    }
    x[n] = m[c] ? 1 : 0;
}

int main() {
    cin >> c >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    Knapsack(v, w, c, n);
    Traceback(w, c, n, x);
    cout << m[c] << endl;
    for (int i = 1; i <= n; i++) {
        if (x[i] == 1) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

经过优化后，代码的空间复杂度为 O(c)，时间复杂度为 O(cn)。