蓝桥杯 求解 01 背包问题

题目描述

实现一个算法求解 01 背包问题。背包问题的介绍如下：

• 已知一个容量为 total_weighttotalw​eight 的背包，有不同重量不同价值的物品，问怎样在背包容量限制下达到利益最大化。
• 01 背包问题要求每个物品只有一个，可以选择放入或者不放入背包。

背包问题求解方法的介绍如下：

• 用符号 V_iVi​ 表示第 ii 个物品的价值，W_iWi​ 表示第 ii 个物品的体积，V_{i,j}Vi,j​ 表示当前背包容量为 jj 时，前 ii 个物品最佳组合对应的价值。
• 对于当前第 ii 个商品，如果包的容量比该物品体积小，即 j < W_ij<Wi​。那么此时的价值与前 i-1i−1 个的价值是一样的，即 V_{i, j} = V_{i - 1, j}Vi,j​=Vi−1,j​。
• 对于当前第 ii 个商品，如果包的容量能够装下该物品，即 W_i \leq jWi​≤j。此时需要判断装或者不装这个物品的价值对比，选择使价值更大的情况，即 V_{i,j} = \max {(V_i + V_{i - 1,j - W_i}, V_{i - 1, j})}Vi,j​=max(Vi​+Vi−1,j−Wi​​,Vi−1,j​)。

通过最优解回溯法找到解的组成：

• 当 V_{i, j} = V_{i-1, j}Vi,j​=Vi−1,j​时，说明没有选择第 ii 个物品。
• 当 V_{i, j} = V_{i - 1,j - W_i}Vi,j​=Vi−1,j−Wi​​ 时，说明装了第 ii 个商品。
• 从 i，ji，j 的最大值一直遍历到 i＝0i＝0 ，则找到了所有解。

输入描述

第一行为两个数字 total_weight、Ntotalw​eight、N，均不超过 1000。total_weighttotalw​eight 含义见题干，NN 为物品数量。

接下来 NN 行，每行两个数字 W_iWi​、V_iVi​，均不超过 1000。含义见题干。

输出描述

输出一行，为在背包容量限制下的最大化利益。

输入输出样例

示例

输入

8 5
3 4
5 5
1 2
2 1
2 3

输出

10

#include<bits/stdc++.h>
using namespace std;
int w[1010];
int v[1010];
int dp[1010][1010]; 
int main(){
    int m,n;
    cin>>m>>n;
    for(int i = 0; i < n; i ++){
        cin>>w[i]>>v[i];
    }
    for(int i = 0; i < n; i ++){
        for(int j = 0; j <= m; j ++){
            if(j < w[i]){
                dp[i + 1][j] = dp[i][j] ;
            }else{
                dp[i + 1][j] = max(dp[i][j],dp[i][j - w[i]] + v[i]);
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

题目链接:求解 01 背包问题 - 蓝桥云课 (lanqiao.cn)