1613: 贪心算法：部分背包问题
金币值：1
定数：1
时间限制：1.000 s
内存限制：128 M
正确：57
提交：114
正确率：50.00% 命题人：
题目描述
给定n 个物品，第i个物品的重量为wi，价值为vi，和一个容量为c的背包。每个物品只能选择一次，但可以选择物品的一部分，价值根据选择的重量比例计算，问背包中物品的最大价值。
要求：使用贪心算法。
快速排序样本代码如下：
// 交换两个元素的函数
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 分区函数，用于将数组分为两部分
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 小于基准的元素的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于等于基准
if (arr[j] <= pivot) {
i++; // 增加小于基准的元素的索引
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// 分区操作
int pi = partition(arr, low, high);
// 递归排序左右两部分
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 分区函数，用于将数组分为两部分
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 小于基准的元素的索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于等于基准
if (arr[j] <= pivot) {
i++; // 增加小于基准的元素的索引
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// 分区操作
int pi = partition(arr, low, high);
// 递归排序左右两部分
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
输入格式
三行：
第一行：整数n，背包容量c
第二行：n个整数，表示n个物品的重量
第三行：n个整数，表示n个物品的价值
输出格式
一个整数。如果计算结果为小数，取整数部分。
输入样例 复制
5 40
10 5 15 10 30
20 30 15 30 10输出样例 复制
95