完全背包问题动态规划c++代码

以下是完全背包问题的动态规划实现的C代码：

#include<stdio.h>
#define MAXN 1000   //物品的最大数量
#define MAXV 1000   //背包的最大容量
int dp[MAXV+1];     //dp[i]表示容量为i的背包所能装下物品的最大价值
int v[MAXN];        //v[i]表示第i个物品的体积
int w[MAXN];        //w[i]表示第i个物品的价值
int n;              //物品的数量
int m;              //背包的容量
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d %d",&v[i],&w[i]);
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(v[j]<=i){
                dp[i]=max(dp[i],dp[i-v[j]]+w[j]);
            }
        }
    }
    printf("%d",dp[m]);
    return 0;
}

注：本代码中使用了max函数，需要先进行定义，可以使用以下代码实现：

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

相关问题

完全背包问题动态规划c++代码，并输出选取物品

以下是完全背包问题的动态规划c代码，同时输出选取的物品：

#include <stdio.h>

int max(int a, int b) {
    if(a > b) return a;
    else return b;
}

int main() {
    int n, m;
    printf("请输入物品个数n和背包容量m：\n");
    scanf("%d%d", &n, &m);

    int w[n], v[n];
    printf("请输入每个物品的重量和价值：\n");
    for(int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    int dp[m+1];
    int selected[n][m+1]; // 记录每个物品是否被选中

    for(int i = 0; i <= m; i++) {
        dp[i] = 0;
    }

    for(int i = 0; i < n; i++) {
        for(int j = w[i]; j <= m; j++) {
            if(dp[j] < dp[j-w[i]] + v[i]) {
                dp[j] = dp[j-w[i]] + v[i];
                // 更新被选中的物品
                for(int k = 0; k < n; k++) {
                    if(j-w[i] >= w[k]) {
                        selected[i][j] = (selected[k][j-w[i]] == 1 || selected[i][j] == 1) ? 1 : 0;
                    }
                    else if(j-w[i] == 0) {
                        selected[i][j] = 1;
                    }
                }
            }
        }
    }

    printf("选中的物品为：\n");
    for(int i = 0; i < n; i++) {
        if(selected[i][m] == 1) {
            printf("第%d个物品\n", i+1);
        }
    }

    printf("最大价值为：%d\n", dp[m]);

    return 0;
}

在上述代码中，我们使用了一个二维数组selected来记录每个物品是否被选中。在更新dp值的同时，我们也更新了selected数组。最后，我们遍历selected数组，输出被选中的物品即可。

完全背包问题c++代码

以下是完全背包问题的 C++ 代码，使用动态规划实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<int> dp(W + 1, 0);

    for (int i = 0; i <= W; i++) {
        for (int j = 0; j < n; j++) {
            if (wt[j] <= i) {
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j]);
            }
        }
    }

    return dp[W];
}

int main() {
    int W = 50;
    vector<int> wt = {10, 20, 30};
    vector<int> val = {60, 100, 120};
    int n = wt.size();

    cout << knapsack(W, wt, val, n) << endl;

    return 0;
}

其中，`W` 表示背包的容量，`wt` 和 `val` 分别表示物品的重量和价值，`n` 表示物品的数量。`dp` 数组表示当前容量下能够获得的最大价值。通过两层循环，不断更新 `dp` 数组，最终返回 `dp[W]` 表示容量为 `W` 时能够获得的最大价值。