2、贪心策略实现背包问题 测试数据：c=6，n=3。 （wi，vi）|（1,3）,（3,6）,（5,9） Knapsack(n, c,v, w, x) 结果:输出最优解和最优值 c语言实现（不是0-1背包）

在背包问题中，贪心策略通常用于解决完全动态背包问题，即物品可以取任意数量。对于给定的测试数据（c=6, n=3），物品和它们的价值和重量分别是（1, 3）、（3, 6）和（5, 9），我们可以使用贪心算法来尝试找到总重量不超过背包容量c的最大价值物品组合。这里简单描述一种基本思路：

1. 按照单位重量价值排序：计算每个物品的价值密度 vi/wi，将物品按这个比例从高到低排列。

2. 依次选择物品：遍历排序后的物品列表，每次选择当前剩余容量范围内价值最高的物品，直到无法再装入任何物品为止。

由于这不是0-1背包问题，物品可以无限多次取用，所以贪心策略在这种情况下通常能够得到全局最优解。假设我们按照上述方法进行，可能会得到这样的结果：

- 首先选择物品（5, 9），因为它的单位重量价值最高（1.8）；
- 容量减少至1（初始为6），然后选择物品（1, 3），因为这是剩余容量下价值最大的（3/1）；
- 此时已经无法再装入物品，背包已满。

最优解将是物品（5, 9）和（1, 3），总价值为9+3=12。下面是简单的C语言实现（注意这仅是一个简化的示例，实际实现可能需要考虑边界条件等细节）：

#include <stdio.h>

// 贪心选择函数
void greedy_knapsack(int v[], int w[], int n, int c) {
    int i;
    for (i = 0; i < n && w[i] <= c; ++i) { // 取物品直到超过容量
        if (v[i] * w[i] > v[0] * c) { // 更新最优解
            v[0] = v[i];
            c -= w[i]; // 减去物品重量
        }
    }
}

int main() {
    int c = 6, n = 3;
    int v[] = {3, 6, 9}; // 物品价值
    int w[] = {1, 3, 5}; // 物品重量
    int opt_val = v[0], opt_weight = w[0];

    greedy_knapsack(v, w, n, c);
    printf("最优解: (%d, %d)\n", opt_weight, opt_val);
    printf("最优值: %d\n", opt_val);

    return 0;
}