#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;
}