01 背包问题和完全背包

Problem Description

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

Input

输入的第一行为T，表示测试数据的组数。对于每组测试数据的第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)，第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

Output

对于每组测试数据输出仅一行，一个数，表示最大总价值。

Sample Input

Sample Output

12
【代码】

#include<iostream>
#include<cstdio>
using namespace std;
int w[20],v[20],f[20];
int main()
{
int m,n;
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
printf("%d",f[m]);
return 0;
}

//判断和不判断的差别 
/*12
1       1       1       1       1       1       1       1       1       0
4       4       4       4       4       4       3       3       1       0
9       9       8       8       6       5       5       3       1       0
12      10      9       9       6       5       5       3       1       0
*/
/*
14
1       1       1       1       1       1       1       1       1       1
4       4       4       4       4       4       4       3       3       3
9       9       9       8       8       8       5       5       5       5
14      14      14      9       9       9       9       9       9       9

*/

//每一件物品的状态抉择为放还是不放如果不放前i件物品不超过v的最大值就是前i-1件物品不超过v的最大值

否则放就是前i-1物品放入 v-w[i]的最大值加上要放入的当前的价值

优化二维数组优化为一维数组 f[v]为重量不超过v的最大值

【代码】

#include<iostream>
#include<cstdio>
using namespace std;
int w[20],c[20],f[20][20];
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int v=m;v>0;v--)
        {
            if(w[i]<=v)//必须要判断 
            f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
            else
            f[i][v]=f[i-1][v];
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

完全背包

【代码】

二维

#include<iostream>
#include<cstdio>
using namespace std;
int w[20],f[20][20],c[30];
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(w[i]>j)
            f[i][j]=f[i-1][j];
            else
            if(f[i-1][j]>f[i-1][j-w[i]]+c[i])
            f[i][j]=f[i-1][j];
            else
            f[i][j]=f[i-1][j-w[i]]+c[i];
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

一维

#include<iostream>
#include<cstdio>
using namespace std;
int f[20],w[20],c[20];
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&w[i],&c[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=w[i];j<=m;j++)
        {
            if(f[j]<f[j-w[i]]+c[i])
            f[j]=f[j-w[i]]+c[i];
        }
    }
    printf("%d",f[m]);
    return 0;
}

数据其实没多大用这数据。。。。

12（二维）
0       1       1       1       1       1       1       1       1       1
0       1       3       3       4       4       4       4       4       4
0       1       3       5       5       6       8       8       9       9
0       1       3       5       5       6       9       9       10      12
  

12（一维）
0       1       3       5       5       6       9       10      10      12

01背包和完全背包的区别是完全背包每种物品有无数件所以每次决策就改变了不在是取或不取而是取几件、

分析一下代码发现两个代码很像区别就是01背包体积循环是 v--1,而完全背包是1--v

why？

为什么01逆序完全顺序

先讲01如果顺序后会怎样呢？

我们知道f[v]=max(f[v],f[v-w[i]]+c[i]);如果顺序1--v，因为f[v]是由f[v-w[i]]推过来的，如果顺序的话 f[v-w[i]]一定推完了我们可能在f[v-w[i]]时就已经

放入了i物品，所以你推的f[v]就拿了两件i物品了，所以01要逆推，，，反之，，拿好几件就是完全顺推了。。。。

我也刚懂。。。糊里糊涂的。。。自己好好想想吧QAQ