蓝桥杯 求解完全背包问题

题目描述

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

• 已知一个容量为 totalw​eight 的背包，有不同重量不同价值的物品，问怎样在背包容量限制下达到利益最大化。
• 完全背包问题的每个物品可以无限选用

输入描述

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

接下来 N 行，每行两个数字 Wi​、Vi​，均不超过 1000。含义见题干。

输出描述

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

输入输出样例

示例

输入

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

输出

16

#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 + 1][j - w[i]] + v[i]);
            }
        }
    }
    cout<<dp[n][m];
    return 0;
}

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