优化这段代码 #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; }

这段代码的优化主要在于使用一维数组代替二维数组，可以减小空间复杂度。另外，对于Traceback函数，可以直接在Knapsack函数中完成，无需单独写一个函数。

以下是优化后的代码：

#include <iostream>
#include <vector>

using namespace std;

void Knapsack(vector<int>& v, vector<int>& w, int c, int n) {
    vector<int> m(c+1);
    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]);  // 状态转移方程
        }
    }
    cout << "最大价值：" << m[c] << endl;

    cout << "所选物品编号：";
    for (int i = 1; i <= n; i++) {
        if (c >= w[i] && m[c] == m[c-w[i]] + v[i]) {
            cout << i << " ";
            c -= w[i];
        }
    }
    cout << endl;
}

int main() {
    int C, n;  // 背包容量，物品数量
    cin >> C >> n;

    vector<int> w(n+1), v(n+1);  // 物品重量和价值
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }

    Knapsack(v, w, C, n);

    return 0;
}

希望能对你有所帮助！