完全背包问题的c++题解

完全背包问题（0-1 Knapsack Problem）是一个经典的动态规划问题，其目标是在给定物品的价值和重量限制下，找出能够装入背包的最大价值组合。以下是简单的C++代码实现：

#include <iostream>
using namespace std;

int knapSack(int W, int wt[], int val[], int n) {
    int K[n+1][W+1];
    
    // Build table K[][] in bottom up manner
    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[] = {60, 100, 120};
    int value[] = {10, 20, 30};
    int capacity = 500;
    int num_items = sizeof(weight)/sizeof(weight[0]);

    cout << "Maximum value that can be put in a bag of capacity " << capacity << ": "
         << knapSack(capacity, weight, value, num_items);

    return 0;
}

在这个例子中，`knapSack`函数通过二维数组`K`存储了从0到当前物品个数和容量的所有可能状态，最后返回的就是最大价值。`main`函数则给出了具体的物品重量（weight）、价值（value）和背包容量（capacity），并调用了这个函数。