帮我补充代码中__的缺失 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为M,应如何选择装入背包的物品,使得装入背包中物品的总价值最大。 贪心算法如下: float greedy_knapsack(float M,float w[],float p[],float x[]) { //x[]背包问题最优解, w[ ]物品重量,P[]物品价值 int n=w.length; float pp=0; float mm=M; //pp计算当前总价值,mm背包剩余载重 for( int i=1;i<=n; i++ ) { float ww[i]=____; //计算物品单位价值ww[ ] x[i]=0; } //初始化 Mergesort(w[], n); //按单位价值ww[]将物品降序, 便于贪心选择 for(int i=1; i<=n; i++ ) {//贪心选择,总是选择价值最大放入背包 if(w[i]<=mm) {//当前物品小于背包剩余载重 x[i]=1; mm=____; pp=____; } else { x[i]=mm/w[i]; pp=____; break; } //i部分放入背包 } return pp; }

补充代码：

float greedy_knapsack(float M, float w[], float p[], float x[]) {
    int n = sizeof(w) / sizeof(float);
    float pp = 0;
    float mm = M;
    float ww[n];
    for (int i = 0; i < n; i++) {
        ww[i] = p[i] / w[i]; //计算物品单位价值
        x[i] = 0;
    }
    //按单位价值降序排序
    Mergesort(ww, n);
    for (int i = n-1; i >= 0; i--) { //降序排序后从大到小依次选择
        if (w[i] <= mm) {
            x[i] = 1;
            mm -= w[i];
            pp += p[i];
        } else {
            x[i] = mm / w[i];
            pp += x[i] * p[i];
            break;
        }
    }
    return pp;
}

在这个代码中，我们首先计算每个物品的单位价值ww[i]，然后按照单位价值从大到小排序。然后从大到小依次选择物品放入背包中，直到背包没有容量为止。如果当前物品不能完全放入背包，只放入一个部分。最后返回背包中物品的总价值。

相关问题

给定n种物品和一个背包,物品i的重量是wi,其价值为vi,问如何选择装入背包的物品,使

以下是两种解决背包问题的算法：

1. 0/1背包问题
0/1背包问题是指每种物品仅有一件，可以选择放或不放。用动态规划求解时，设v[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值有以下状态转移方程：
v[i][j] = max{v[i-1][j], v[i-1][j-w[i]] + v[i]} (j>=w[i])
其中，w[i]和v[i]分别表示第i件物品的重量和价值。

2. 完全背包问题
完全背包问题是指每种物品有无限件，可以选择放或不放。同样用动态规划求解时，设v[i][j]表示前i件物品放入容量为j的背包可以获得的最大价值，则有以下状态转移方程：
v[i][j] = max{v[i-1][j-k*w[i]] + k*v[i]} (0<=k*w[i]<=j)
其中，w[i]和v[i]仍然表示第i件物品的重量和价值。

给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为c。问应如何选择

给定n种物品和一个背包，每种物品i的重量是wi，其价值为vi，背包的容量为c。我们需要选择哪些物品放入背包，以便背包中物品的总价值最大。

解决这个问题可以使用动态规划的方法。我们定义一个二维数组dp，其中dp[i][j]表示在背包容量为j的情况下，前i种物品的最大总价值。

我们可以通过以下步骤来填充dp数组：
1. 初始化dp数组为0.
2. 从第1种物品开始遍历到第n种物品：
- 对于每一种物品i，遍历背包容量从1到c：
- 如果wi > j，则物品i无法放入背包中，dp[i][j]等于dp[i-1][j].
- 否则，比较物品i放入背包和不放入背包的情况：
- 如果将物品i放入背包，总价值为dp[i-1][j-wi] + vi.
- 如果不放入物品i，总价值为dp[i-1][j].
- 选择其中较大的总价值作为dp[i][j]的值。
3. 返回dp[n][c]作为结果，即表示在背包容量为c的情况下，前n种物品的最大总价值。

这样，我们可以得到最优解。这个算法的时间复杂度是O(n*c)，其中n是物品的数量，c是背包的容量。