用bp表解决完全背包问题，求出最优解是如何包装：v1 = 1, v2 = 3, v3 = 5, v4 = 9 重量：w1 = 2, w2 = 3, w3 = 4, w4 = 7 背包容量：b = 10 用C++写

为了用回溯法（Backtracking）解决完全背包问题，并找到最优解，我们可以创建一个二维布尔数组`dp`，其中`dp[i][j]`表示是否能用前i个物品填充容量为j的背包。以下是使用C++实现的一个简单版本：

#include <iostream>
#include <vector>

// 定义物品信息和背包容量
struct Item {
    int value;
    int weight;
};

Item items[] = { {1, 2}, {3, 3}, {5, 4}, {9, 7} }; // v1, v2, v3, v4, w1, w2, w3, w4
const int numItems = sizeof(items) / sizeof(items[0]);
int capacity = 10; // b

// 回溯函数，递归地尝试组合
bool backtrack(int i, int j, std::vector<bool>& dp) {
    if (i == numItems || j < 0) return false;

    // 如果当前物品放进去，背包还能装下一个
    if (j >= items[i].weight && dp[i - 1][j - items[i].weight])
        dp[i] = true;

    // 不放当前物品，继续尝试其他组合
    dp[i] |= backtrack(i + 1, j, dp);

    return dp[i];
}

// 检查背包能否填满以及得到最大价值
void solve() {
    std::vector<bool> dp(numItems + 1, false);
    if (backtrack(0, capacity, dp)) {
        int maxValue = 0;
        for (int i = 0; i <= numItems; ++i)
            if (dp[i])
                maxValue += items[i].value;
        std::cout << "Optimal solution with a total value of " << maxValue << std::endl;
    } else {
        std::cout << "No feasible solution found." << std::endl;
    }
}

int main() {
    solve();
    return 0;
}

这个程序会遍历所有可能的物品组合，找出背包能够达到的最大总价值。运行此程序后，你会看到最优解决方案及其总价值。注意，这种方法并不保证最优解是最少步骤的组合，因为它是基于价值最大化而不是步数最小化。