nyoj 106 背包问题（dp或贪心都可）

阳光穿透心脏的1/2处 2022-03-28 03:39 198阅读 0赞

*  题目106
 *  [题目信息][Link 1]
 *  [运行结果][Link 2]
 *  [本题排行][Link 3]
 *  [讨论区][Link 4]

####  ####

## 背包问题 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

输入

第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；  
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。

输出

输出每组测试数据中背包内的物品的价值和，每次输出占一行。

样例输入

1
    3 15
    5 10
    2 8
    3 9

样例输出

来源

[\[苗栋栋\]原创][Link 5]

上传者

先上贪心的

#include <iostream>
    #include <algorithm>
    using namespace std;
    struct pack
    {
        int v;
        int w;
    };
    bool cmp(pack m,pack n)
    {
        return m.v>n.v;
    }
    int main()
    {
        pack *p;
        int i,n,s,m,sum;
        cin>>n;
        while(n--)
        {
             cin>>s>>m;
             sum=0;
             p=new pack[s];
             for(i=0;i<s;i++)
             {
                 cin>>p[i].v>>p[i].w;
             }
             sort(p,p+s,cmp);
             for(i=0;i<s;i++)
             {
                 if(m-p[i].w>0)
                 {
                     sum+=p[i].v*p[i].w;
                     m-=p[i].w;
                 }
                 else{sum+=m*p[i].v;break;}
                 }
                 cout<<sum<<endl;
                 delete[] p;
         }
    return 0;
    }

动态规划的

#include<stdio.h>
    #define max(a,b) a>b?a:b
    int main()
    {
        int n,s,m,v,w,i,j,k;
        scanf("%d",&n);
        while(n--)
        {
            int DP[25]={0};
            scanf("%d %d",&s,&m);
            for(i=0;i<s;i++)
            {
                scanf("%d %d",&v,&w);
                for(k=0;k<w;k++)
                for(j=m;j>0;j--)
                    DP[j]=max(DP[j-1]+v,DP[j]);
            }
            printf("%d\n",DP[m]);
        }
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/problem.php?pid=106
[Link 2]: http://acm.nyist.net/JudgeOnline/status.php?pid=106
[Link 3]: http://acm.nyist.net/JudgeOnline/problemrank.php?pid=106
[Link 4]: http://acm.nyist.net/JudgeOnline/talking.php?pid=106
[Link 5]: http://acm.nyist.net/JudgeOnline/search_result.php?source=%5B%E8%8B%97%E6%A0%8B%E6%A0%8B%5D%E5%8E%9F%E5%88%9B