现有n种物品和一个可承载M 重量的背包，n种物品的重量分别为(w 1 ​ , w 2 ​ , …, w n ​ )，n种物品放入背包所获得的效益分别是(p 1 ​ , p 2 ​ , …, p n ​ ) (p i ​ >0)，p i ​ 和w i ​ 均是正整数，若将物品i的一部分x i ​ (0<=x i ​ <=1)放入背包，则所获得的效益是p i ​*x i ​ ，问采用怎样的装包方法会使装入背包物品的总效益为最大？输入格式: 第1行是M和n，表示背包容量为M且有n件物品； 第2行是这n件物品的重量w i ​ ； 第3行是各物品的价值p i ​ 。 输出格式: 第1行是所选物品的最大价值之和； 第2行是各物品装入背包的量x i ​ 。要求保留小数点后两位，第三位按照四舍五入处理。用C语言实现

以下是 C 语言实现代码：

#include <stdio.h>

#define MAX_N 1000

int n, m;
int w[MAX_N], p[MAX_N];
double x[MAX_N], f[MAX_N];

void zero_one_pack(int i, int value) {
    for (int j = m; j >= w[i]; j--) {
        double new_f = f[j - w[i]] + p[i] * value;
        if (new_f > f[j]) {
            f[j] = new_f;
            x[i] = value;
        }
    }
}

void multiple_pack(int i) {
    for (int j = w[i]; j <= m; j++) {
        double new_f = f[j - w[i]] + p[i];
        if (new_f > f[j]) {
            f[j] = new_f;
            x[i] = 1.0;
        }
    }
}

int main() {
    scanf("%d %d", &m, &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }

    for (int i = 1; i <= n; i++) {
        if (w[i] == 1) {
            zero_one_pack(i, 1);
        } else if (w[i] * 3 >= m) {
            multiple_pack(i);
        } else {
            for (int k = 1; k <= w[i]; k <<= 1) {
                zero_one_pack(i, k);
                w[i] -= k;
            }
            if (w[i] > 0) {
                zero_one_pack(i, w[i]);
            }
        }
    }

    double ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += x[i] * p[i];
    }

    printf("%.2f\n", ans);

    for (int i = 1; i <= n; i++) {
        printf("%.2f ", x[i]);
    }
    printf("\n");

    return 0;
}

算法思路：

- 对于重量为 1 的物品，使用 01 背包算法进行处理；
- 对于重量大于 $\frac{1}{3}M$ 的物品，使用完全背包算法进行处理；
- 对于重量介于 1 和 $\frac{1}{3}M$ 之间的物品，分别对其进行拆分，使用多重背包算法进行处理。

其中，对于重量介于 1 和 $\frac{1}{3}M$ 之间的物品，我们采用了拆分的策略。对于一个重量为 $w_i$ 的物品，我们可以将其拆分成 $2^k$ 个重量为 $2^k$ 的物品和一个重量为 $w_i - 2^k$ 的物品，这样可以保证每次使用的重量都是 2 的幂次方，可以大大提高算法效率。

时间复杂度：$O(nm\log w)$

空间复杂度：$O(m)$