背包九讲之完全背包详解

2019-11-28 16:36:53 浏览数 (1)

1：问题描述：

南阳理工acm上的类型题。http://acm.nyist.net/JudgeOnline/problem.php?pid=311

完全背包

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

难度：4

描述直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出NO

输入第一行： N 表示有多少组测试数据（N<7）。

接下来每组测试数据的第一行有两个整数M，V。 M表示物品种类的数目，V表示背包的总容量。(0<M<=2000，0<V<=50000)

接下来的M行每行有两个整数c，w分别表示每种物品的重量和价值(0<c<100000，0<w<100000)输出对应每组测试数据输出结果（如果能恰好装满背包，输出装满背包时背包内物品的最大价值总和。 如果不能恰好装满背包，输出NO）样例输入

代码语言：javascript复制
2
1 5
2 2
2 5
2 2
5 1

样例输出

代码语言：javascript复制
NO
1

2：问题解析

背包是否要装满，问法不同？

有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

因为初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

O(VN)的算法

这个算法使用一维数组，先看伪代码：

for i=1..N

for v=0..V

f[v]=max{f[v],f[v-cost] weight}

你会发现，这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

3：结题代码

代码语言：javascript复制
#include<stdio.h>
#include<string.h>
int i,j,c[100001],w[100001];//可以优化，可以去掉数组，每接收一个就计算一个。
int main()
{
    int m;
    int n,v;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&n,&v);
        memset(c,0,sizeof(c));
        memset(w,0,sizeof(w));
        int f[50005]={0};
        for(i = 1 ; i < 50005 ; i  )//设定-无穷值。可以用memset(f,-100,sizeof(f))替代
            f[i] = -123123123;
        for(i = 1 ; i <= n ; i  )
            scanf("%d %d",&c[i],&w[i]);
        for(i = 1 ; i <= n ; i  )
            for(j = c[i]; j <= v; j  )//关键的顺序修改
                if(f[j-c[i]] w[i]>f[j])
                    f[j] = f[j-c[i]] w[i];
        if(f[v]<0) printf("NOn");
        else printf("%dn",f[v]);
    }
}

4：过程分析。

还是模拟算出f[i]的值就可以理解。

首先拿例题来：

  • 1 5
  • 2 2

可以获取出N = 1，V= 5，c[i]={2}.w[i]={2},f[0]=0,f[i]=负无穷;

大脑计算机启动啦。

  • for i=1..N
  • for v=c[i]->V
  • f[v]=max{f[v],f[v-c[i]] w[i]};

当 i=1 ;v=2到5

  • f[2] = max{f[2],f[2-2] 2}因为f[0] = 0,f[2]=负无穷所以f[2] = 2;
  • f[3] = max{f[3],f[3-2] 2}因为f[1] = -负无穷,f[3]=负无穷所以f[3] = 负无穷;
  • f[4] = max{f[4],f[4-2] 2}因为f[2] = 2,f[4]=负无穷所以f[4] = 4；
  • f[5] = max{f[5],f[5-2] 2}因为f[3] = 负无穷,f[5]=负无穷所以f[5] = 负无穷;

最后输出f[v] =负无穷。输出NO。

原创文章，转载请注明： 转载自URl-team

本文链接地址: 背包九讲之完全背包详解

No related posts.

acm max

0 人点赞