蓝桥杯算法训练VIP-入学考试 （C++代码）

解题思路:其实就是01背包问题





注意事项:





参考代码:

#include <deque>

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <iterator>

#include <iomanip>

#include <numeric>

#include <sstream>

#include <string>

#include <cmath>

#include <string.h>

#define  V 1001 

using namespace std;

unsigned int f[101][V];//全局变量，自动初始化为0  

unsigned int weight[101];  

unsigned int value[101];  

#define  max(x,y)   (x)>(y)?(x):(y)  

int main()  

{       

    int N,M;  

    cin>>M;//背包容量  

    cin>>N;//物品个数  

    for (int i=1;i<=N; i++)  

    {  

        cin>>weight[i]>>value[i];  

    }  

    for (int i=1; i<=N; i++)  

        for (int j=1; j<=M; j++)  

        {  

            if (weight[i]<=j)  

            {  

                f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i]);  

            }  

            else  

                f[i][j]=f[i-1][j];  

        }    

    cout<<f[N][M]<<endl;//输出最优解  

}