sort(w + 1, w + 1 + n); //将物品按重量从小到大排序，为什么使用w+1

在 C++ 中，数组名就是数组首元素的地址。因此，`w+1` 表示指向 `w` 数组中第二个元素的指针（因为数组下标从 0 开始），`w+1+n` 则表示指向 `w` 数组中第 `n+1` 个元素的指针。

将 `w+1` 传入 `sort()` 函数中，是因为 `sort()` 函数默认从第一个元素开始排序。如果直接传入 `w`，则第一个元素会被视为一个极大值，导致排序出错。因此，我们需要将指针指向第二个元素，即 `w+1`，从而使排序正常进行。

相关问题

请用c语言实现以下问题：给定n个重量为w1，w2，w3，…，wn，价值为v1，v2，v3，…，vn的物品以及容量为C的背包，求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大。 分别采用价值最大、重量最小、价值率最大原则实现贪心算法，写出相应程序。

以下是采用三种贪心算法实现0/1背包问题的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 100 // 物品的最大数量
#define C 100 // 背包的最大容量

// 物品结构体
typedef struct {
    int w; // 重量
    int v; // 价值
    float r; // 价值重量比
} Item;

// 按价值从大到小排序
void sort_by_value(Item *items, int n) {
    int i, j;
    Item tmp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (items[j].v < items[j + 1].v) {
                tmp = items[j];
                items[j] = items[j + 1];
                items[j + 1] = tmp;
            }
        }
    }
}

// 按重量从小到大排序
void sort_by_weight(Item *items, int n) {
    int i, j;
    Item tmp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (items[j].w > items[j + 1].w) {
                tmp = items[j];
                items[j] = items[j + 1];
                items[j + 1] = tmp;
            }
        }
    }
}

// 按价值重量比从大到小排序
void sort_by_ratio(Item *items, int n) {
    int i, j;
    Item tmp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (items[j].r < items[j + 1].r) {
                tmp = items[j];
                items[j] = items[j + 1];
                items[j + 1] = tmp;
            }
        }
    }
}

// 采用价值最大原则的贪心算法
int greedy_by_value(Item *items, int n, int c, int *selected) {
    sort_by_value(items, n);
    int i, j, total_value = 0;
    memset(selected, 0, sizeof(int) * n);
    for (i = 0; i < n; i++) {
        if (c < items[i].w) break;
        selected[i] = 1;
        c -= items[i].w;
        total_value += items[i].v;
    }
    return total_value;
}

// 采用重量最小原则的贪心算法
int greedy_by_weight(Item *items, int n, int c, int *selected) {
    sort_by_weight(items, n);
    int i, j, total_value = 0;
    memset(selected, 0, sizeof(int) * n);
    for (i = 0; i < n; i++) {
        if (c < items[i].w) break;
        selected[i] = 1;
        c -= items[i].w;
        total_value += items[i].v;
    }
    return total_value;
}

// 采用价值重量比最大原则的贪心算法
int greedy_by_ratio(Item *items, int n, int c, int *selected) {
    sort_by_ratio(items, n);
    int i, j, total_value = 0;
    memset(selected, 0, sizeof(int) * n);
    for (i = 0; i < n; i++) {
        if (c < items[i].w) break;
        selected[i] = 1;
        c -= items[i].w;
        total_value += items[i].v;
    }
    return total_value;
}

int main() {
    int n, c, i, value;
    Item items[N];
    int selected[N];
    printf("请输入物品数量n和背包容量c：\n");
    scanf("%d %d", &n, &c);
    printf("请依次输入每个物品的重量w和价值v：\n");
    for (i = 0; i < n; i++) {
        scanf("%d %d", &items[i].w, &items[i].v);
        items[i].r = (float)items[i].v / items[i].w;
    }
    value = greedy_by_value(items, n, c, selected);
    printf("采用价值最大原则的贪心算法，总价值为：%d\n", value);
    value = greedy_by_weight(items, n, c, selected);
    printf("采用重量最小原则的贪心算法，总价值为：%d\n", value);
    value = greedy_by_ratio(items, n, c, selected);
    printf("采用价值重量比最大原则的贪心算法，总价值为：%d\n", value);
    return 0;
}

注意，以上代码仅仅是贪心算法的实现，如果要得到最优解，需要使用动态规划算法。

最优装载问题： 问题描述：某艘船的载重量为C，每件物品的重量为wi，要将尽量多的物品装入到船上。请给出c++代码

以下是使用贪心算法解决最优装载问题的C++代码：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    const int MAXN = 1000;
    int n, c, w[MAXN];
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    sort(w, w + n); // 将物品按重量从小到大排序
    int sum = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        if (sum + w[i] <= c) { // 如果当前物品能装下
            sum += w[i]; // 更新当前载重量
            cnt++; // 更新已装载物品数量
        } else {
            break; // 否则退出循环
        }
    }
    cout << cnt << endl; // 输出已装载物品数量
    return 0;
}

该算法的时间复杂度为 $O(n \log n)$，其中 $n$ 为物品数量。