0
다음은 동적 프로그래밍 알고리즘을 사용하여 0-1 배낭 문제를 해결하는 C++ 프로그램입니다. Keep은 항목이 최대 답변에 포함되었는지 여부 (1과 0 사용)를 유지하는 2D 배열입니다. 실행시 프로그램은 컴파일하지만 다음과 같은 오류를 제공합니다 : '표준 : length_error' 의 인스턴스를 던지는 후 호출 종료 무엇을() : basic_string :: _ S_create 중단 여기프로그램이 실행될 때 중지, 0-1 백팩
내 코드입니다 :
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
static ifstream fr;
static vector<int> stolen_Profit;
static vector<int> stolen_Weight;
static vector<string> stolen_Name;
/**class for item object*/
class Item
{
public:
/**constructor that will get information from the file*/
Item()
{
fr>>name>>p>>w;
r=p/w;
}
/**@return the name of the item object*/
string getName()
{return name;}
/**@return the weight of the item object*/
int getWeight()
{return w;}
/**@return the weight of the item object*/
int getProfit()
{return p;}
/**@return the weight of the item object*/
double getRatio()
{return r;}
private:
string name;
double r;
int w, p;
};
int max(int a, int b)
{
int max=a;
if (b>a)
{max=b;}
return max;
}
void finditems(int remainingweight, int item, int **Keep, int Weight[], int Profit[], string Name[])
{
if (item!=0)
{
if(Keep[item][remainingweight]==1)
{
stolen_Weight.push_back(Weight[item]);
stolen_Profit.push_back(Profit[item]);
stolen_Name.push_back(Name[item]);
remainingweight=remainingweight-Weight[item];
item=item-1;
finditems(remainingweight,item, Keep, Weight, Profit, Name);
//add the item to stolen
}
if(Keep[item][remainingweight]==0)
{
item=item-1;
finditems(remainingweight,item, Keep, Weight, Profit, Name);
}
}
else return;
}
void knapsack(int n, int W, int Weight[], int Profit[], string Name[], int *P[], int *Keep[])
{
//set all values in the 0 row to 0
for(int i=0; i<=W; i++)
{
P[0][i]=0;
Keep[0][i]=0;
}
for(int i=0; i<=n; i++)
{
//set all values in the 0 weight column to 0
P[i][0]=0;
Keep[i][0]=0;
for (int j=1; j<=W; j++)
{
if (Weight[i]<=j)
{
P[i][j]= max(P[i-1][j], Profit[i] + P[i-1][j-Weight[i]]);
if (P[i][j]==P[i-1][j])
{Keep[i][j]=0;}
else
Keep[i][j]=1;
}
else
P[i][j]=P[i-1][j];
Keep[i][j]=0;
}
}
finditems(W, n, Keep, Weight, Profit, Name);
int totalweight=0;
/**print out information to output file*/
ofstream fw;
fw.open("outputp1.txt");
//# of items in solution
cout<<stolen_Name.size()<<endl;
//total weight
for(int i=0; i<stolen_Weight.size(); i++)
{
totalweight=totalweight+stolen_Weight[i];
}
cout<<totalweight<<endl;
//total profit
cout<<P[n][W]<<endl;
//print out the information of each item
for(int i=0; i<stolen_Name.size(); i++)
{cout<< stolen_Name[i]<<" "<< stolen_Profit[i] << " "<< stolen_Weight[i]<<endl;}
fw.close();
}
int main()
{
int n, W;
fr.open("inputp1.txt");
fr>>n>>W;
/**create an array of Items objects based on n*/
Item tosteal[n];
int *Profit=new int[n+1];
int *Weight=new int[n+1];
string *Name=new string[n+1];
for (int i=0; i<=n; i++)
{
if (i==0)
{
Profit[i]=0;
Weight[i]=0;
Name[i]="";
}
else
Profit[i]= tosteal[i-1].getProfit();
Weight[i]= tosteal[i-1].getWeight();
Name[i]= tosteal[i-1].getName();
}
int **P= new int *[n+1];
int **Keep= new int *[n+1];
for (int i=0; i<=n; i++)
{
P[i]=new int [W];
Keep[i]=new int [W];
}
fr.close();
knapsack(n, W, Weight, Profit, Name, P, Keep);
cout <<"Solution to 0-1 Knapsack Problem written to file."<<endl;
//garbage collection
for (int i=0; i<=n;i++)
{
delete P[i];
delete Keep[i];
}
delete P;
delete Keep;
delete Weight;
delete Profit;
delete Name;
//delete stolen_Name;
//delete stolen_Profit;
//delete stolen_Weight;
}