01背包问题递归c++程序

下面是一个用递归实现 01背包问题 的 C++ 程序：

#include <iostream>
using namespace std;

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

int knapSack(int W, int wt[], int val[], int n) {
    // 递归终止条件
    if (n == 0 || W == 0)
        return 0;

    // 如果当前物品的重量大于背包的容量，则不能放入背包中
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);

    // 返回不选当前物品和选当前物品中的最大值
    else
        return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
                   knapSack(W, wt, val, n - 1));
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    cout << knapSack(W, wt, val, n) << endl;
    return 0;
}

在上面的程序中，`knapSack()` 函数是递归函数，输入参数包括背包的容量 `W`，物品的重量 `wt[]`，物品的价值 `val[]`，以及物品的数量 `n`。递归终止条件是物品数量为 0 或者背包容量为 0。如果当前物品的重量大于背包的容量，则不能放入背包中；否则返回不选当前物品和选当前物品中的最大值。在主函数中，我们使用了一个简单的例子来测试上述函数。