用贪心法实现背包问题和动态规划法实现0-1背包问题并给出c++代码

**贪心法 - 背包问题（Best Fit 或 First Fit）**

由于贪心法不一定能得到0-1背包问题的全局最优解，这里我们可以讨论非贪婪版本的First Fit，但它一般适用于物品的单位价值与其重量相等的情况。

#include <iostream>
using namespace std;

bool canFit(int weight[], int value[], int capacity, int n, int i) {
    return capacity >= weight[i];
}

void firstFit(int weight[], int value[], int capacity, int n) {
    for (int i = 0; i < n && capacity > 0; ++i) {
        if (canFit(weight, value, capacity, n, i)) {
            cout << "Adding item " << i+1 << " of weight " << weight[i] << " and value " << value[i] << endl;
            capacity -= weight[i]; // 使用物品
        }
    }
}

int main() {
    int weight[] = {10, 20, 30};
    int value[] = {60, 100, 120};
    int capacity = 50;
    int n = sizeof(weight)/sizeof(weight[0]);
    firstFit(weight, value, capacity, n);
    return 0;
}

**动态规划 - 0-1背包问题（Knapsack Problem）**

以下是使用动态规划实现0-1背包问题的C++代码：

#include <iostream>
using namespace std;

int knapSack(int W, int wt[], int val[], int n) {
    int K[n+1][W+1];

    for (int i=0; i<=n; i++) {
        for (int w=0; w<=W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i-1] <= w)
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); // 如果选则物品，考虑不选
            else
                K[i][w] = K[i-1][w]; // 否则直接保留前一项的最优解
        }
    }

    return K[n][W];
}

int main() {
    int weight[] = {10, 20, 30};
    int value[] = {60, 100, 120};
    int capacity = 50;
    int n = sizeof(weight)/sizeof(weight[0]);
    cout << "Max Value using 0-1 Knapsack: " << knapSack(capacity, weight, value, n) << endl;
    return 0;
}

请注意，以上代码仅作为示例，实际应用中应处理边界条件和异常情况。