背包九讲--完全背包

完全背包

【问题描述】
　　 设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
【输入格式】
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；
第2…N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。
【输出格式】
仅一行，一个数，表示最大总价值。
【样例输入】knapsack.in
10 4
2 1
3 3
4 5
7 9
【样例输出】knapsack.out
　 max=12

【简化版视频讲解及代码】

#include<cstdio>
using namespace std;
const int maxm=2001,maxn=31;
int n,m,v,i;
int c[maxn],w[maxn];
int f[maxm];

int main()
{
    scanf("%d%d",&m,&n);            //背包容量m和物品数量n
    for(i=1;i<=n;i++)                  //背包容量m和物品数量n
        scanf("%d%d",&w[i],&c[i]);
    for(i=1;i<=n;i++)
        for(v=w[i];v<=m;v++)          //设 f[v]表示重量不超过v公斤的最大价值
            if(f[v-w[i]]+c[i]>f[v])  f[v]=f[v-w[i]]+c[i];
    printf("max=%d\n",f[m]);           // f[m]为最优解
    return 0;
}

【详细原理讲解及核心推导过程】

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i = 1 ; i <= n ;i ++)
    {
        cin>>v[i]>>w[i];
    }

    for(int i = 1 ; i<=n ;i++)
    for(int j = 0 ; j<=m ;j++)
    {
        for(int k = 0 ; k*v[i]<=j ; k++)
            f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    }

    cout<<f[n][m]<<endl;
}

下面的推导很重要

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)

由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
于是就可以优化成上面的一维标准代码了！不懂一定要看视频哦！

01背包与完全背包的区别与联系

1、01背包中的物品只有一件，只有取与不取两种选择，而完全背包中的物品有无限多个，有不取，取1件、2件…n件
2、代码核心区别在于01背包内层循环逆序遍历，完全背包顺序遍历

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
//完全背包问题

完全背包练习题目

1、疯狂采药
视频讲解
2、货币系统
3、飞扬的小鸟