#include

#define N 5 // 物品数量

#define W 10 // 背包容量

int v_temp[N + 1], w_temp[N + 1]; // 物品价值数组 和 物品重量数组的临时数组

double vw_temp[N + 1]; // 物品单位重量价值数组的临时数组

double answer[N + 1]; // 解方案数组

// 归并排序

void merge_sort(int v[], int w[], double vw[], int l, int r) {

if (l >= r) return;

int mid = l + r >> 1;

merge_sort(v, w, vw, l, mid), merge_sort(v, w, vw, mid + 1, r);

int i = l, j = mid + 1, k = 1;

while (i

vw_temp[k] = vw[j];

v_temp[k] = v[j];

w_temp[k] = w[j];

k ++ , j ++ ;

}

}

while (i

vw_temp[k] = vw[j];

v_temp[k] = v[j];

w_temp[k] = w[j];

k ++ , j ++ ;

}

for (i = l, j = 1; i

int i;

printf("物品价值数组：");

for (i = 1; i

if (W_temp >= w[i]) { // 当前背包容量 大于等于 物品重量 就直接全部装入到背包中

answer[i] = 1.0;

result = result + v[i];

W_temp = W_temp - w[i];

} else { // 当前背包容量 小于 物品重量 就应该将该物品的一部分装入到背包中

break;

}

}

if (W_temp > 0 && i