背包问题（Knapsack Problem）是一类组合优化的问题。在这类问题中，你给定一组项目，每个项目都有各自的重量和价值，并且你需要选择一些项目装入背包，以使得背包中的总价值最大，同时不超过背包的重量限制。背包问题有多种变种，最常见的两种是0/1背包问题和分数背包问题。

0/1背包问题

在0/1背包问题中，每个项目要么被完整地选择，要么完全不选，不能分割。这是背包问题中最著名的变种，可以使用动态规划解决。

动态规划解决方案：

1. 定义状态：dp[i][j] 表示在前i个物品中选择，且总重量不超过j时能达到的最大价值。
2. 状态转移方程：
   
3. 初始状态：dp[0][j] = 0，表示没有物品时，价值为0。
4. 边界条件：dp[i][0] = 0，表示重量为0时，无论有多少物品，价值都为0。

int knapsack01(int n, int weights[], int values[], int W) {
    int j;
    int i;
    int dp[n+1][W+1];

    // 基础情况
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= W; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
        }
    }

    // 填表
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= W; j++) {
            if (weights[i-1] <= j)
                dp[i][j] = std::max(dp[i-1][j],
                                     dp[i-1][j-weights[i-1]] + values[i-1]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }

    return dp[n][W];
}

分数背包问题

在分数背包问题中，物品可以分割成任意大小，即可以选择物品的一部分来达到最优解。

贪心解决方案：

1. 排序：按照物品的价值密度（价值除以重量）对物品进行排序。
2. 选择：依次考虑排序后的物品，尽可能多地选择价值密度最高的物品，直到超过背包重量限制。

struct Item {
    int value;
    int weight;
    double ratio;
};

bool compareItems(Item a, Item b) {
    return a.ratio > b.ratio;
}

int fractionalKnapsack(int n, Item items[], int W) {
    std::sort(items, items + n, compareItems);

    int i = 0;
    int totalValue = 0;
    while (i < n && W > 0) {
        int curWeight = std::min(W, items[i].weight);
        totalValue += curWeight * items[i].ratio;
        W -= curWeight;
        i++;
    }
    return totalValue;
}

背包问题的变种：

• 多重背包问题：每个物品有数量限制，可以多次选择。
• 分组背包问题：物品被分为不同的组，每组内的物品只能选择一个。

背包问题是组合优化问题的一个典型例子，广泛应用于资源分配、调度、网络路由等领域。动态规划和贪心算法是解决背包问题最常用的两种方法。