代码语言：c++

所属分类：算法

代码描述：c++解决01背包问题示例代码，01背包问题就是你需要选择一组物品放入一个背包，以使它们的总价值最大化，同时不超过背包的容量限制。

代码标签： c++ 解决 01 背包 问题 示例 代码

下面为部分代码预览，完整代码请点击下载或在bfwstudio webide中打开

#include <iostream>
#include <vector>

using namespace std;

int knapsack(int capacity, vector < int>& values, vector < int>& weights, vector < int>& selectedItems) {
    int n = values.size();
    vector < vector < int > > dp(n + 1, vector < int > (capacity + 1, 0));
    vector < vector < bool > > keep(n + 1, vector < bool > (capacity + 1, false));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                int withCurrentItem = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                int withoutCurrentItem = dp[i - 1][w];
                if (withCurrentItem > withoutCurrentItem) {
                    dp[i][w] = withCurrentItem;
                    keep[i][w] = true;
                } else {
                    dp[i][w] = withoutCurrentItem;
                    keep[i][w] = false;
                }
            } else {
                .........完整代码请登录后点击上方下载按钮下载查看

网友评论0

取消

评论提交中...

提交评论