美文网首页
蓝桥杯练习7(0-1背包)

蓝桥杯练习7(0-1背包)

作者: Cipolee | 来源:发表于2019-03-17 16:28 被阅读0次

    原创

    0-1背包是动态规划里重要的一种题型,身为计算机人怎能不熟悉dp?

    问题描述
      给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
    输入格式
      输入的第一行包含两个整数n, m,分别表示物品的个数和背包能装重量。
      以后N行每行两个数Wi和Vi,表示物品的重量和价值
    输出格式
      输出1行,包含一个整数,表示最大价值。
    样例输入
    3 5
    2 3
    3 5
    4 7
    样例输出
    8
    数据规模和约定
      1<=N<=200,M<=5000.

    易知这种题具有最优子结构,且子问题重叠,具有一定的递归形式,可使用dp。
    使用备忘录方法,初始化一数组为0;使用<string>中的memset(数组名,0,sizeof(数组名)),把每一种往背包里放东西的当前状态都选择为最优。

    代码如下:

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>//动态规划必须对数组进行初始化,一般使用<string>里的memset函数进行初始化
    using namespace std;
    int main()
    {
        int n,m;
        cin>>n>>m;
        int dp[m+5];
        memset(dp,0,sizeof(dp));
        int w,v;
        while(n--)
        {
            cin>>w>>v;
            for(int j=m;j>=w;j--)
            {
                dp[j]=max(dp[j],dp[j-w]+v);
            }
        }
        cout<<dp[m];
        return 0;
    }
    
    

    相关文章

      网友评论

          本文标题:蓝桥杯练习7(0-1背包)

          本文链接:https://www.haomeiwen.com/subject/kmpumqtx.html