{

int weight;

int value;

{

//对每个item进行判断

int maxValue = 0;

for (int i = 0; i < itemCnt; i++)

{

if (itemList[i].weight <= index)

{

int valueCandidate = bag[index - itemList[i].weight] + itemList[i].value;

if (maxValue < valueCandidate)

maxValue = valueCandidate;

}

}

bag[index] = maxValue;

{

knapsack *itemList;

int itemCnt;

//输入物品个数

cout << "输入物品的个数: ";

cin >> itemCnt;

itemList = new knapsack[itemCnt];

//输入物品重量和价值

cout << "输入物品的重量和价值(w v): \n";

for (int i = 0; i < itemCnt; i++)

cin >> itemList[i].weight >> itemList[i].value;

//输入背包容量

int bagCapacity;//背包容量

cout << "输入背包容量: ";

cin >> bagCapacity;

//动态规划的辅助变量

int *bag = new int[bagCapacity+1];//bag[i]表示容量i时可装的最大价值

for (int i = 0; i <= bagCapacity; i++)

bag[i] = 0;

//开始动态规划

for (int i = 0; i <= bagCapacity; i++)

{

KnapsackWithRepo(itemList, bag, i,itemCnt,bagCapacity);

}

for (int i = 0; i <= bagCapacity; i++)

cout << bag[i] << " ";

cout << "\n最大容量为" << bag[bagCapacity];

return 0;

}