C语言递归方法求解背包问题
C语言递归方法求解背包问题,编译环境vs2019
上问题:
十、背包问题的求解
假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品,能否从n件物品中挑选若干件恰好装满背包,即使w1 +w2 + … + wn=T,要求找出所有满足上述条件的解。例如:当T=10,各件物品的体积{1,8,4,3,5,2}时,可找到下列4组解:
(1,4,3,2)
(1,4,5)
(8,2)
(3,5,2)。
上代码:
#include<stdio.h>
int answer[100] = {
0 };//保存结果
int p = 0;//answer的指针
void bag(int *nums, int locate, int total, int len, int big) {
for (int i = locate; i < len; i++) {
total += answer[p++] = nums[i];//total取和,answer保存当前的数
if (total < big) {
//比背包小的时候进入递归
bag(nums, i + 1, total, len, big);
total -= answer[--p];//递归结束减去当前数,准备进入下一次循环
}
else if (total > big)//比背包大
total -= answer[--p];
else if (total == big) {
//和背包相等打印结果
for (int j = 0; j < p; j++)
printf("%d ", answer[j]);
printf("\n");
total -= answer[--p];
}
}
}
void main() {
int nums[] = {
1,8,4,3,5,2 }, big = 10, total = 0, len = sizeof(nums)/sizeof(int), locate = 0;
bag(nums, locate, total, len, big);
}