部分背包问题c语言

部分背包问题是指有一组物品，每种物品都有自己的重量和价值，在限定的总重量内，选择其中若干个物品，使得物品的总价值最大。

这可以使用贪心算法来解决，但是贪心算法不能保证得到全局最优解。因此，可以使用动态规划来解决部分背包问题。

以下是部分背包问题的动态规划代码实现：

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

#define MAX_WEIGHT 100   // 背包的最大重量
#define MAX_N 100        // 物品的最大数量

int weight[MAX_N];    // 物品的重量
int value[MAX_N];     // 物品的价值
float density[MAX_N]; // 物品的单位价值
int dp[MAX_WEIGHT+1]; // 动态规划数组

int max(int a, int b) {
    return a > b ? a : b;
}

void dynamic_programming(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = MAX_WEIGHT; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
        }
    }
}

int main() {
    int n; // 物品数量
    printf("请输入物品数量：");
    scanf("%d", &n);

    printf("请依次输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
        density[i] = (float)value[i] / weight[i];
    }

    // 根据单位价值排序
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            if (density[i] < density[j]) {
                float temp = density[i];
                density[i] = density[j];
                density[j] = temp;

                int temp2 = weight[i];
                weight[i] = weight[j];
                weight[j] = temp2;

                temp2 = value[i];
                value[i] = value[j];
                value[j] = temp2;
            }
        }
    }

    dynamic_programming(n);

    printf("最大价值为：%d\n", dp[MAX_WEIGHT]);

    return 0;
}

在该代码中，首先输入物品数量和每个物品的重量和价值。然后根据物品的单位价值排序，之后使用动态规划解决部分背包问题，最后输出最大价值。