c++ 背包问题 小内存

Question

帮本蒟蒻看看吧

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, W;
    cin >> n;

    vector<int> w(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    cin >> W;

    vector<vector<int> > table(n+1, vector<int>(W+1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (w[i-1] > j) {
                table[i][j] = table[i-1][j];
            } else {
                table[i][j] = max(w[i-1] + table[i-1][j-w[i-1]], table[i-1][j]);
            }
        }
    }

    int max_weight = table[n][W];
    cout << max_weight << endl;

    vector<int> items;
    int i = n, j = W;
    while (i > 0 && j > 0) {
        if (table[i][j] == table[i-1][j]) {
            i--;
        } else {
            items.push_back(i);
            j -= w[i-1];
            i--;
        }
    }

    int num_items = items.size();
    cout << num_items << endl;

    for (int i = num_items-1; i >= 0; i--) {
        cout << items[i] << " ";
    }
    cout << endl;

    return 0;
}

请大家们提提修改意见，主要是内存超限，帮我看看吧！

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/335034
• 这篇博客你也可以参考下：C++ 基类中静态成员初始化问题、基类头文件中定义类外变量重定义问题的解决过程
• 除此之外, 这篇博客: C++实现单链表的基本运算中的 头节点不包含数据，具有指引作用，头节点的下一个结点才开始保存数据。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  void CreateListR(LinkList *&L,ElemType a[],int n)
  {
  	LinkList *s,*r;int i;
  	L=new LinkList;  //产生一个新的头结点
  	r=L;  //令r指针指向终端结点，刚开始的时候指向头结点
  	for(i=0;i<n;i++)
  	{
  		s=new LinkList;
  		s->data=a[i];
  		r->next=s;  //将s插入r的后面
  		r=s;     //r指针指向终端结点
  	}
  	r->next=NULL;
  }

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^