逃亡的准备
分类:关于计算机

Description

  在《哈利 Potter and the Deathly 哈尔lows》中,HarryPotter他们一块逃脱,今后有那一个的事物要松手赫敏的包里面,可是包的轻重有限,所以我们只好够在内部放入极度首要的物料,未来交付该种货物的数目、容积、价值的数值,希望您可知算出哪些能使手拿包的价值最大的结缘措施,而且输出这些数值,赫敏会非常地感谢您。

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

12个价值为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;
}

本文由正版必中一肖图发布于关于计算机,转载请注明出处:逃亡的准备

上一篇:ui引入后Vs2008的无智能提示问题解决方法,ui引入 下一篇:没有了
猜你喜欢
热门排行
精彩图文