0-1背包问题

[zhw-zhw]

[zhw-zhw]

#include
using namespace std;
#include

int knapsackdp(int n,int *p,int *v,int c)
{
static int P[6][14];//备忘录数组
static int Rec[6][14];//用来追踪最优方案
//初始化
for(int i=0;i<=c;i++)
{
P[0][i]=0;
Rec[0][i]=0;
}
for(int i=0;i<=n;i++)
{
P[i][0]=0;
Rec[i][0]=0;
}
//求解表格
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;j++)
{
if(v[i]<=j&&(p[i]+P[i-1][j-v[i]])>P[i-1][j])
{
P[i][j]=p[i]+P[i-1][j-v[i]];
Rec[i][j]=1;
}
else
{
P[i][j]=P[i-1][j];
Rec[i][j]=0;

        }
    }
}

//输出最优方案
int k=c;
for(int i=n;i>=1;i--)
{
    if(Rec[i][k]==1)
    {
        cout<<"选择了商品 "<<i<<endl;
        k=k-v[i];
    }
    else
    {
        cout<<"没有选择商品 "<<i<<endl;
        
    }
}

//输出数P和数组Rec
cout<<"数组 P:"<<endl;

 for(int i=0;i<=n;i++)
{
    for(int j=0;j<=c;j++)
    {

        cout<<left<<setw(4)<<P[i][j];
    }
    cout<<endl;
}

cout<<"数组 Rec:"<<endl;

for(int i=0;i<=n;i++)
{
    for(int j=0;j<=c;j++)
    {

        cout<<left<<setw(4)<<Rec[i][j];
    }
    cout<<endl;
}

return P[5][13];

}

int main()
{
int n=5,c=13;//有5件商品，背包的容量为13；
int p[6]={0,24,2,9,10,9};
int v[6]={0,10,3,4,5,4};
int s= knapsackdp(n,p,v,c);
cout<<"背包中能装入的最大价值为 "<<s<<endl;
}