DP复习——完全背包

完全背包

完全背包，就是有n$n$种物品，每种物品每个都有一个重量wi$w_i$和一个价值vi$v_i$，每种物品都有足够多个，还有一个m$m$容量的背包。我们的任务就是取若干个物品，在∑所取的w[i]<=m$\sum _{所取的}w[i]<=m$的情况下，最大化∑所取的v[i]$\sum _{所取的}v[i]$。

例题

题目描述
有一个负重能力为m(m<=300)的背包和n(n<=100)种物品，第i种物品的价值为v[i]，重量为w[i]。在不超过背包负重能力的前提下选择若干个物品装入背包，使这些物品的价值之和最大。每种物品可以不选，也可以选择多个。假设每种物品都有足够的数量。
输入格式
第1行 m n 第2行到n+1行 每行两个数据，分别为每种物品的重量和价值，空格隔开。
输出格式
装入背包物品的最大价值
样例数据
input
12 4
2 1
3 3
4 5
7 9
output
max=15

题解

板子题，直接上代码。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int num=0;
    char c=' ';
    bool flag=true;
    for(;c>'9'||c<'0';c=getchar())
    if(c=='-')
    flag=false;
    for(;c>='0'&&c<='9';num=num*10+c-48,c=getchar());
    return flag ? num : -num;
}
const int maxn=102;
const int maxm=302;
int n,m,v[maxn],w[maxn],f[maxn*maxm];
void init()
{
    m=read();
    n=read();
    for(int i=1;i<=n;i++)
    {
        w[i]=read();
        v[i]=read();
    }
}
void DP()
{
    for(int i=1;i<=n;i++)
    for(int j=w[i];j<=m;j++)
    //这里是和01背包唯一不一样的地方
    //因为每种物品可以取不只一次
    //所以每个容量可以更新一次以上
    //所以就可以这样玩。
    f[j]=max(f[j],f[j-w[i]]+v[i]);
    printf("max=%d\n",f[m]);
}
int main()
{
    init();
    DP();
    return 0;
}