背包九讲之01背包详解

01背包是基础的背包题，最近需要详细的在实验室算法交流会上讲解，so，从原理到实现都从学一遍背包问题。

1：问题描述：

南阳理工acm上的类型题。

http://acm.nyist.net/JudgeOnline/problem.php?pid=289

苹果

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

难度：3

描述ctest有n个苹果，要将它放入容量为v的背包。给出第i个苹果的大小和价钱，求出能放入背包的苹果的总价钱最大值。

输入有多组测试数据，每组测试数据第一行为2个正整数，分别代表苹果的个数n和背包的容量v，n、v同时为0时结束测试，此时不输出。接下来的n行，每行2个正整数，用空格隔开，分别代表苹果的大小c和价钱w。所有输入数字的范围大于等于0，小于等于1000。输出对每组测试数据输出一个整数，代表能放入背包的苹果的总价值。样例输入

3 3
1 1
2 1
3 1
0 0

样例输出

2

2：问题解析

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

方法的时间复杂度为O(N*V)，空间复杂度可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符。

3：结题代码

01背包

#include<stdio.h>
int main()
{
    int n,v;
    while(scanf("%d%d",&n,&v)&&(n+v))
    {
        int i,j,k,c[1001],w[1001],f[1000]={0};//这里的初始化是全部为0，因为不是刚好装满，而是价值最大。
        for(i = 1 ; i <= n ; i++)
            scanf("%d %d",&c[i],&w[i]);
        for(i = 1 ; i <= n ; i++)
            for(j = v; j >= c[i]; j--)//这里是核心，一定是要从v开始递减。意味着能把每一种已经算过的情况再算上一遍。算是搜索。
                if(f[j-c[i]]+w[i]>f[j])//这if就是状态转移方程。如果装这个物品的收益大于不装这个物品，则装他。
                    f[j] = f[j-c[i]]+w[i];
        printf("%d\n",f[v]);
    }
}

4：过程分析。

要学会这个01背包的运作原理，就必须让大脑当成计算机走一遍，

首先拿例题来：

• 3 3
• 1 1
• 2 1
• 3 1

可以获取出n = 3，v= 3，c[i]={1,2,3}.w[i]={1,1,1};

大脑计算机启动啦。

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

当 i=1 ;v=3到1

• f[3] = max{0,f[2]+1}因为f[2] = 0所以f[3] = 1;
• f[2] = max{0,f[1]+1}因为f[1] = 0所以f[2] = 1;
• f[1] = max{0,f[0]+1}因为f[0] = 0所以f[1] = 1;

当 i=2 ;v=3到2

• f[3] = max{1,f[1]+1}因为f[1] = 1所以f[3] = 2;
• f[2] = max{1,f[0]+1}因为f[0] = 0所以f[2] = 1;

当 i=3;v=3到3

• f[3] = max{2,f[0]+1}因为f[0] = 0所以f[3] = 2;

最后输出f[v] =2

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

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

No related posts.