1. 编写程序使用回溯算法求解0/1背包问题,并用实际的数据进行测试。
2. 采用基于迭代的回溯算法求解。
四、实验步骤
1. 编写函数KNAPSACK求解0/1背包问题,函数头为:
void KNAPSACK(int v[], int s[], int C, int n)
其中s[]中存储每件物品的体积,v[]中存储每件物品的价值,n为物品数量,C为背包容量。
2. 在main函数中使用给定数据进行测试,数据如下:
s[] = {3,5,7,8,9};v[] = {4,6,7,9,10};C = 11;
求背包能够装载物品的最大价值,效果如下图所示。