lalalala


私信TA

用户名:zhangshuo

访问量:151550

签 名:

像狗一样的学习,像绅士一样地玩耍。

等  级
排  名 5
经  验 30087
参赛次数 10
文章发表 201
年  龄 12
在职情况 学生
学  校 芜湖市第十一中学
专  业

  自我简介:

今日懒惰流下的口水,将会成为明日里伤心的泪水。


这道题看似是搜索,但是可以用背包做。

题目要求求出最小的剩余空间,也就是要求出最大的可装重量

这样,我们可以将一个物体的重量当作它的价值,进而将题目转变为一个基本的01背包问题:

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)和一个价值(等于体积)。

要求n个物品中,任取若干个装入箱内,使总价值最大。

对于每一个物体,都有两种状态:装 与不装

那么,对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )(w为重量(即价值))

其中,f ( m - w[i] ) 指在装了物品i后,箱子的剩余容量能装的最大重量

f ( m - w[i] ) + w[i] 指在在装了物品i后,箱子能装的最大重量

程序如下:

#include<cstdio>
using namespace std;
int m,n;//m即箱子容量V
int f[20010];
int w[40];
int main()
{    
   int i,j;    
   scanf("%d%d",&m,&n);    
   for(i=1;i<=n;i++)
    {        
       scanf("%d",&w[i]);
    }
       for(i=1;i<=n;i++)
       {        
           for(j=m;j>=w[i];j--)
           {                            //注意:这里必须是从m到w[i],否则一个物体会被多次装入箱子,见例1
                if(f[j]<f[j-w[i]]+w[i])
                   {
                       f[j]=f[j-w[i]]+w[i];
                    }
            }
       }    
     printf("%d\n",m-f[m]);
}
 

0.0分

2 人评分

  评论区