逃亡的准备

2018-06-17 21:27:57来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Description

  在《Harry Potter and the Deathly Hallows》中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限,所以我们只能够在里面放入非常重要的物品,现在给出该种物品的数量、体积、价值的数值,希望你能够算出怎样能使背包的价值最大的组合方式,并且输出这个数值,赫敏会非常地感谢你。

Input

(1)第一行有2个整数,物品种数n和背包装载体积v。 
(2)2行到n+1行每行3个整数,为第i种物品的数量m、体积w、价值s。

Output

仅包含一个整数,即为能拿到的最大的物品价值总和。

Sample Input

2 10
3 4 3
2 2 5

Sample Output

13

Hint

【注释】 
选第一种一个,第二种两个。 
结果为3*1+5*2=13 

【数据规模】 
对于30%的数据 
1<=v<=500 
1<=n<=2000 
1<=m<=10 
1<=w<=20 
1<=s<=100 

对于100%的数据 
1<=v<=500 
1<=n<=2000 
1<=m<=5000 
1<=w<=20 
1<=s<=100 

 (第一篇博客文章,有点小激动)

这道题一看就是一道DP题;

多重背包。

第一眼看不难

 但,

这道题要优化一下,不优化好像会超时的~~

二进制法

x=2^0+2^1+2^2+......+y

举个栗子:

13=2^0+2^1+2^2+6

13个价值为v,体积为w的物品

可“捆绑”为4个物品

          价值             体积 

1          v                   w

2         2v                 2w

3         4v                 4w

4         6v                 6w

这四个就可以组合为全部13以内个数的物品

比如:用7个可以  1号+6号

         用11个可以 4号+3号+1号

        ……………………………………

  这样“捆绑”一下就可以省去不少时间了(13重→4重~~)

 

源代码:

#include<bits/stdc++.h>
using namespace std;
int a[6010],w[6010],v[6010],f[6010];
int n,m;
int main()
{
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    cin>>a[i]>>w[i]>>v[i];
  for(int i=1;i<=n;i++)
  {
    if(a[i]*w[i]>=m)     //完全背包问题
    {
      for(int j=w[i];j<=m;j++)
      {
        f[j]=max(f[j],f[j-w[i]]+v[i]);
      }
    }
    else
    {
      int k=1,aa=a[i];
      for(;k<aa;)
      {
        for(int j=m;j>=k*w[i];j--)
        {
          f[j]=max(f[j],f[j-w[i]*k]+v[i]*k);
        }
        aa-=k;
        k+=k;
      }
      for(int j=m;j>=w[i]*aa;j--)        //01背包,剩下的一并处理;

        f[j]=max(f[j],f[j-w[i]*aa]+v[i]*aa);
    }
  }
  sort(f+1,f+m+1);
  cout<<f[m]<<endl;
}

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:面向对象程序设计的4个主要特点

下一篇:c++ 随机函数用法