|
发表于 2024-6-1 17:18:01
|
显示全部楼层
好的,我们来编写一个用回溯法解决0-1背包问题的C程序。
首先,我们需要定义一个结构体来表示每个物品的重量和价值:
- typedef struct {
- int weight; // 物品的重量
- int value; // 物品的价值
- } Item;
复制代码
然后,我们需要定义一些全局变量来存储问题的输入和输出:
- #define MAX_ITEMS 100 // 最大物品数量
- int numItems; // 物品数量
- int maxWeight; // 背包的最大承重
- Item items[MAX_ITEMS]; // 物品数组
- int bestValue; // 最佳方案的总价值
- int currValue; // 当前方案的总价值
- int currWeight; // 当前方案的总重量
- int selected[MAX_ITEMS]; // 当前方案中选中的物品
- int bestSelection[MAX_ITEMS]; // 最佳方案中选中的物品
复制代码
接下来,我们需要编写一个递归函数来尝试所有可能的选择,并更新最佳方案。我们将使用深度优先搜索的方式进行搜索。具体实现如下:
- void backtrack(int depth) {
- if (depth == numItems) {
- if (currValue > bestValue) {
- bestValue = currValue;
- for (int i = 0; i < numItems; i++) {
- bestSelection[i] = selected[i];
- }
- }
- return;
- }
- // 选择当前物品
- if (currWeight + items[depth].weight <= maxWeight) {
- selected[depth] = 1;
- currWeight += items[depth].weight;
- currValue += items[depth].value;
- backtrack(depth + 1);
- currWeight -= items[depth].weight;
- currValue -= items[depth].value;
- }
- // 不选择当前物品
- selected[depth] = 0;
- backtrack(depth + 1);
- }
复制代码
最后,我们编写一个主函数来读取输入并调用回溯函数:
- int main() {
- printf("请输入物品数量:");
- scanf("%d", &numItems);
- printf("请输入背包的最大承重:");
- scanf("%d", &maxWeight);
- for (int i = 0; i < numItems; i++) {
- printf("请输入第%d个物品的重量和价值,以空格分隔:", i + 1);
- scanf("%d %d", &items[i].weight, &items[i].value);
- }
- bestValue = 0;
- currValue = 0;
- currWeight = 0;
- memset(selected, 0, sizeof(selected));
- memset(bestSelection, 0, sizeof(bestSelection));
- backtrack(0);
- printf("最佳方案的总价值:%d\n", bestValue);
- printf("选中的物品列表:");
- for (int i = 0; i < numItems; i++) {
- if (bestSelection[i])
- printf("%d ", i + 1);
- }
- printf("\n");
- return 0;
- }
复制代码
这样,我们就完成了一个使用回溯法解决0-1背包问题的C程序。希望对你有帮助!
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。 |
|