1

这是我目前正在使用的代码

template <class T>
float Knapsack<T>::knapTable()
{
  const int MAXSIZE = 40000;
  int temps = nObjects - 1;
  float** memoize = new float*[MAXSIZE];

  for(int y = 0; y < weight[nObjects]; y++)
    memoize[nObjects][y] = 0;

  for(int y = weight[nObjects]; y < knapCap; y++)
    memoize[nObjects][y] = price[y];

  for(int i = temps; i >= 1; i--)
  {
    for(int y = weight[i]; y < knapCap; y++)
      memoize[i][y]= max(memoize[i+1][y], (memoize[i+1][y-weight[i]]+price[i]));
  }

  return memoize[1][nObjects];

}

出于某种原因，我不断收到错误消息：knapsack.hpp:68:64: error: invalid types 'float*[float]' for array subscript。

就是这一行： float** memoize = new float*[MAXSIZE];

由于某种原因，编译器似乎将 MAXSIZE 识别为浮点数，它是一个 const int。

有没有办法解决这个问题？

编辑了更多代码头文件#ifndef KNAPSACK_H #define KNAPSACK_H

#include <stdexcept>
#include <assert.h>
#include <iostream>
#include <limits.h>
using namespace std;

template <class T>
class Knapsack
{
  private:
    float knapPrice;
    int knapCap, nObjects;
    float weight[40000];
    float price[40000];
  public:

    Knapsack(): knapPrice(0), knapCap(0), nObjects(0) {}
    ~Knapsack() {knapPrice = 0; knapCap = 0;}

    float knapFull (int position, int currentCap);

    float knapTable ();

    float greedyKnap (int currentCap);

    float max(float noAdd,float addOb);

    void printPrice();
    //valueized and valued are modified versions of mergeSort and merge
    //designed to sort two arrays by a fraction of the two.
    void valueize(int ini, int last);

    void valued(int ini, int middle, int last);

    void fillWandP();

    void setNObjects(int n);

    void setKnapCap(int boom);
};
#include "knapsack.hpp"
#endif

主函数 //虽然我不认为这会影响它 #include "sortClass.h" #include "knapsack.h" #include #include #include #include using namespace std;

//mergeSort main;
int main()
{
    Knapsack<float> a;
    float sacked = 0;

    int nO = 18;
    int cap = 700;
    a.setNObjects(nO);

a.setKnapCap(cap);

    a.fillWandP();

    for(int b = 0; b <3800000; b++)//for getting good times
  sacked = b;

    int startAll = clock()*1000000;
    sacked = a.knapFull(1, cap);
    int knapped = clock()*1000000;
    int boom = a.knapTable();
    int tabled = clock()*1000000;
    a.valueize(1, cap);
    int andDone = a.greedyKnap(cap);
    int greedified = clock()*1000000;
    cout<<startAll<<endl;

    greedified = greedified - tabled;
    tabled = tabled - knapped;
    knapped = knapped - startAll;
    cout<<"Recursion profit:"<<sacked<<" Time: "<<knapped<<endl;
    cout<<"Memoization profit:"<<boom<<" Time: "<<tabled<<endl;
    cout<<"Greedy profit: "<<andDone<<" Time: "<<greedified<<endl;



    return 0;
}
4

4 回答 4

2

weight被声明float weight[40000]为class Knapsack。

然后在函数中使用一个元素weight作为索引：memoizeknaptable()

memoize[i][y]= max(memoize[i+1][y], (memoize[i+1][y-weight[i]]+price[i]));
//                                                  ^^^^^^^^^

作为记录，这就是 g++ 4.6.1 产生错误的那一行；它不指向memoize声明的行。

于 2012-10-31T01:28:10.440 回答
1 
  for(int i = temps; i >= 1; i--)
  {
    for(int y = weight[i]; y < knapCap; y++)
      memoize[i][y]= max(memoize[i+1][y], (memoize[i+1][y-weight[i]]+price[i]));
  }

y-weight[i]是一个浮点数。这是你的问题。

解决此问题后，您会发现仍然存在问题，您正在分配一个指针数组，但您还需要为每个指针分配第二个维度，然后才能使用该数组。

类似于以下内容：

float** memoize = new float*[MAXSIZE];

for(size_t i = 0; i < MAXSIZE; ++i)
{
  memoize[i] = new float[MAXSIZE];
}
于 2012-10-31T01:28:21.043 回答
1

不一定相关，但您没有正确使用数组/指针。您在调用时创建了第一级指针，float** memoize = new float*[MAXSIZE]但是您只有一个指针数组，而不是双精度数组。您还需要将每个初始化memoize[i]为数组。

话虽如此，看起来您memoize无论如何都不应该为您的数组分配内存。只需将其声明为

float memoize[SIZE][SIZE];

这样，您就不必担心内存清理或其他任何事情，而且更有意义。

于 2012-10-31T01:06:57.460 回答
0

我想也许你只需要为第二个指针分配内存，就像

float** memoize = new float*[MAXSIZE];
    memoize=(float**)malloc(sizeof(float*)*MAXSIZE);
    for(int i=0;i<MAXSIZE;i++)
    {
        memoize[i]=(float*)malloc(sizeof(float)*MAXSIZE);
    }
于 2012-10-31T01:28:21.330 回答