给定n种物品和一个容量C=20的背包，物品i的重量是wi，其价值为vi，背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?用C++实现

背包问题（Knapsack Problem），也称为贪婪算法的一个经典例子，是一个典型的动态规划问题。目标是在给定限制条件下，选取一组物品使其总价值最大。在这个场景下，每件物品都有一个重量（wi）和一个单位价值（vi）。标准的0-1背包问题假设物品只能取整数倍，而实际应用中还可能有完全背包版本，允许部分选取。

动态规划通常通过创建一个二维数组dp[i][j]表示前i个物品中有多少重量小于等于j的最大价值，对于每个物品i，有两种选择：放入背包（dp[i-1][j-wi] + vi）或不放（dp[i-1][j]）。最终结果就是dp[n][C]。

以下是用C++实现0-1背包问题的一个基本版：

#include <iostream>
using namespace std;

int knapSack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}

int main() {
    int weights[] = {60, 100, 120}; // 物品重量
    int values[] = {100, 200, 150}; // 物品价值
    int weight_limit = 200; // 背包容量
    int num_items = sizeof(weights)/sizeof(weights[0]);

    cout << "最大价值： " << knapSack(weight_limit, weights, values, num_items);
    return 0;
}