01背包问题回溯法

01背包问题回溯法

#include “iostream“
#include “stdio.h“

#define maxGoodsNum 20
using namespace std;

int num maxValue currentValue currentWeight bagWeight;//物品数量，最大价值，当前价值，当前重量，背包容量
int currentGoods[maxGoodsNum] = { 0 };//背包物品，

struct goods {
	int weight;//物品重量
	int value;//物品价值
	int number;//物体序号，按输入次序排列;从goods[1]开始存放
}goods[maxGoodsNum];

//交换函数
void swap（int& a int& b） {
	int temp;
	temp = a;
	a = b;
	b = temp;
};
void swap（struct goods& good1 struct goods& good2） {
	swap（good1.value good2.value）;
	swap（good1.weight good2.weight）;
	swap（good1.number good2.number）;
}

//排序函数，按单位价值排序
void sort（） {
	int perValue[maxGoodsNum];
	for （int i = 1; i <= num; i++） {
		perValue[i] = goods[i].value / goods[i].weight;
	}
	for （int i = 1; i <= num - 1; i++） {
		for （int j