首页 > 其他 > 详细

1175.开心的金明 01背包

时间:2018-12-15 20:27:06      阅读:226      评论:0      收藏:0      [点我收藏+]

---恢复内容开始---

#include<bits/stdc++.h>
using namespace std;
int a[30050],b[30050];
int mp[30050];
int n,i,tmp,m,j;
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(mp,0,sizeof(mp));
        for(i=1;i<=m;i++)
        {
            scanf("%d %d",&a[i],&b[i]);
        }
        //m[i][j] 表示在面对第i件物品,且背包容量为 j时所能获得的最大价值 
//        //时间复杂度O(N * M),空间复杂度也为O(N * M)
//        for(i=1;i<=m;i++)//物品
//        {
//            for(j=0;j<=n;j++)//资源
//            {
//                if(j>=a[i])mp[i][j]=max(mp[i-1][j],mp[i-1][j-a[i]]+a[i]*b[i]);
//                else mp[i][j]=mp[i-1][j];
//            }
//                
//        }
        //空间复杂度也为O(N)
        for(i=1;i<=m;i++)//物品
        {
            for(j=n;j>=0;j--)//钱数
            {//利用滚动数组求背包问题最合适的值
                if(j-a[i]>=0) mp[j]=max(mp[j],mp[j-a[i]]+a[i]*b[i]);
            }
        }
        cout<<mp[n]<<endl;
    }
    return 0;
}

  

---恢复内容结束---

1175.开心的金明 01背包

原文:https://www.cnblogs.com/guanwen769aaaa/p/10124467.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!