baidu_38729492
baidu_38729492
2017-05-10 06:36

0-1背包问题 C++ 一直编译不通过 求大神指出错误

  • c++
  • 算法设计与分析

#include
using namespace std;

const int MAX = 250;
int V[MAX][MAX];

int max(int a, int b)
{
if (a >= b)
return a;
else
return b;
}

int Knapsack(int n[], int vi[], int c, int x,int choose[])
{
for (int i = 0; i <= x; i++)
V[i][0] = 0;
for (int j = 0; j <= c; j++)
V[0][j] = 0;

for (int i = 1; i <= x; i++)
{
    cout << i << "  " << n[i] << "  " << vi[i]<<"   ";

    for (int j = 1; j <= c; j++)
    {
        if (n[j] > j)
        {
            V[i][j] = V[i - 1][j];
            cout << "[" << i << "]" << "[" << j << "]" << "=" << V[i][j]<<" ";
        }

        else
        {
            V[i][j] = max(V[i - 1][j], V[i - 1][j - n[j]] + vi[i]);
            cout << "[" << i << "]" << "[" << j << "]" << "=" << V[i][j] << "   ";
        }

    }
    cout << endl;
}

int j = c;
for (int i = x; i > 0; i--)
{
    if (V[i][j] > V[i - 1][j])
    {
        choose[i] = 1;
        j = j - n[i];
    }
    else
        choose[i] = 0;
}
for (int i = 1; i <= x; i++)
    cout<< choose[i];
cout << endl;

return V[x][c];

}
int main()
{
int c, x;
cout << "请输入背包容量;";
cin >> c;
cout << "请输入物品个数:";
cin >> x;
int *n = new int[x+1];
int *vi = new int[x+1];
int *choose = new int[x+1];
cout << "请分别输入物品重量";
for (int i = 1; i <= x; i++)
cin >> n[i];
cout << "请分别输入物品价值:";
for (int i = 1; i <= x; i++)
cin >> vi[i];
int k = Knapsack(n, vi, c, x,choose);
cout << "物品最大价值为:" << k << endl;

}

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

2条回答

为你推荐

换一换