完全背包和01背包的区别在于完全背包里的每一件物品的数量有无数个。
模板

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= v; ++j) {
        if (c[i] <= j)
            f[i][j] = max(f[i - 1][j],f[i][j - c[i]] + v[i]);
        else
            f[i][j] = f[i - 1][j];
    }
}

与01背包类似的模板

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

 
 
模板题

极度怀疑这个题目有错看，结果应该是10

//#include <bits/stdc++.h>
int dp[101][101],w[101],v[101];
 //方法一
int main(){
    freopen("data","r",stdin);
    int n,W;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    cin>>W;
    for(int i=0;i<n;i++)
        for(int j=0;j<=W;j++)
            if(j<w[i])
                dp[i+1][j]=dp[i][j];
            else{
                dp[i+1][j]=max(dp[i-1][j],dp[i+1][j-w[i]]+v[i]);
            }
    cout<<dp[n][W];
    return 0;
} 

   //方法二
    for(int i=0;i<n;i++)
        for(int j=w[i];j<=W;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    cout<<dp[W];

 

一大波例题来啦

Piggy-Bank

#include <bits/stdc++.h>
using namespace std;
long long int dp[1000001],w[10000001],v[1000001];

int main(){
freopen("data","r",stdin);
long long int t,weight,W,n;
scanf("%lld",&t);
while(t--){
    
    //dp[0]=0;
    scanf("%lld%lld",&weight,&W);
    W-=weight;
    //切记，这里不能把dp[0]也设置成inf！ 
    for(int i=1;i<=W;i++) dp[i]=1000000000;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld%lld",&v[i],&w[i]);
    for(int i=0;i<n;i++)
        for(int j=w[i];j<=W;j++)
            dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
    
    if(dp[W]==1000000000)
        cout<<"This is impossible."<<endl;
    else
        printf("The minimum amount of money in the piggy-bank is %lld.\n",dp[W]);
}
return 0;
} 

Robberies

这道题很有意思：题目中给定价值和被抓几率，但是被抓几率不可以用乘积来组合计算，举个例子，比如第一个银行3%被抓几率，第二个5%被抓几率，那么乘起来会变成0.15%，抢的越多，被抓几率却越小了，显然不对，因此要转换成不被抓几率，上述例子则变为第一家97%不被抓，第二家95%不被抓，乘起来就是92.15%，抢的越多，不被抓的几率越来越小即被抓几率越来越大，这样才是符合常理的。
因为几率都是小于1的，所以相乘一定会减小，而强的银行越多，被抓率不可能减少//如果是这样，大家都去抢银行了~~

//#include <bits/stdc++.h>
using namespace std;
#define  eps 0.000000000001
double w[10100],W,dp[10100];
int a[10100],n;
int t;
//w[i]是被抓几率，然后转成逃跑几率 
int main(){
//      freopen("data","r",stdin);
    cin>>t;
      while(t--){
        int sum=0;
        memset(dp,0,sizeof(dp));
        scanf("%lf%d",&W,&n);
        //把它变成逃跑几率 
        W=1-W;
        dp[0]=1;//你不抢银行你就不用被抓咯 
        for(int i=0;i<n;i++)
        {
            scanf("%d%lf",&a[i],&w[i]);
            w[i]=1-w[i];
            sum+=a[i];
        }
        for(int i=0;i<n;i++)
//钱数从最多开始循环
            for(int j=sum;j>=a[i];j--)
                dp[j]=max(dp[j],dp[j-a[i]]*w[i]);
            
        for(int i=sum;i>=0;i--){
            if(dp[i]>W){
                printf("%d\n",i);
                break; 
            } 
        }
    
    }
 
    return 0;
} 

 
 

多重背包

例题

珍惜现在，感恩生活

拆分那里刚开始是没有搞懂的，然后看了师兄发的文件，又试着将过程输出了一下，才明白拆分的含义，比如说这道题有四袋米，我可以把它拆成三分，一分是一袋米，一份是两袋米，最后一份还是一袋米（通过补充来计算），将他们存入一个新的数组里面，最后再对这个新的数组进行01背包就可以了嘛~

//#include <bits/stdc++.h>
using namespace std;
int max(int x,int y){
    return x>y?x:y;
}
struct E
{
    int w;  //体积
    int v;  //重量
} lis[2001];

int dp[101];

int main()
{
    int T,n,m;
    int p,h,k;
    int i,j;
    int index,c;
    cin>>T;
    while(T--){
    scanf("%d%d",&n,&m);                //n表示容量，m表示种类
    index = 0;  //拆分后物品总数
    for( i=1; i<=m; i++)
    {
        c = 1;
        scanf("%d%d%d",&p,&h,&k);       //p表示价格，h表示重量，k表示大米袋数。
    //这里开始拆分
        while( k-c>0)
        {
            k -= c;
            lis[++index].w = c*p;
            lis[index].v = c*h;
            c *= 2;
        }
        lis[++index].w = p*k;  //补充不足指数的差值
        lis[index].v = h*k;
    }
    for( i=0; i<=n; i++) dp[i]=0;
    for( i=1; i<=index; i++)   //对拆分后的物品进行0-1背包
    {
        for( j=n; j>=lis[i].w; j--)
            dp[j] = max( dp[j],dp[j-lis[i].w]+lis[i].v);
    }
        printf("%d\n",dp[n]);
    }
    return 0;
}

Coins

其实刚开始看到这个问题时，想到的时完全背包，但是对于一个菜鸟来说，不知道怎么打，然后看了一些大佬的代码，才有了头绪---说是双线背包~
这里的dp起到标记的作用，sum[j]是用来记录每j元需要多少个硬币，ans是用来记录次数。

解法一

//#include <bits/stdc++.h>
using namespace std;
int dp[100001],n,m,v[101],w[101],sum[100001];

int main()
{
    while(cin>>n>>m&&m&&n){
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
            cin>>v[i];
        for(int i=0;i<n;i++)
            cin>>w[i];
        dp[0]=1;
        int ans=0;
        for(int i=0;i<n;i++){
            memset(sum,0,sizeof(sum));
            for(int j=v[i];j<=m;j++){
                //这里进行筛选 
                //sum[j]表示当前物品填充j大小的包需要至少使用多少个.
                if(!dp[j]&&dp[j-v[i]]&&sum[j-v[i]]<w[i]){
                    dp[j]=1;
                    sum[j]=sum[j-v[i]]+1;
                    ans++;
                }
            }
        } 
        cout<<ans<<endl;    
    }
    return 0;
}

解法二（多重部分和）

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
int dp[100001];
int A[100001],C[1001];
int a[4]={0,1,2,5};
int m;
int n,K=15000;

int main()
{
    while(cin>>n>>m&&(n!=0||m!=0)){
        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        for(int i=0;i<n;i++)
            cin>>A[i];
        for(int i=0;i<n;i++)
            cin>>C[i];
        for(int i=0;i<n;i++)
            for(int j=0;j<=m;j++){
                if(dp[j]>=0)
                    dp[j]=C[i];
                else if(A[i]>j||dp[j-A[i]]<=0)
                    dp[j]=-1;
                else
                    dp[j]=dp[j-A[i]]-1;
            }
        int res=0;
        for(int i=1;i<=m;i++){
            if(dp[i]>=0)
                res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

Cash Machine

这道题和第一道例题很像,只不过没有用结构体每一步都是按照模板来滴

//#include <bits/stdc++.h>
using namespace std;
int dp[100001],n,m,v[101],w[101],sum[100001];
int max(int x,int y){
    return x>y?x:y;
}
int main()
{
    freopen("data","r",stdin);
    int cash,num,denomination;
    while(cin>>cash){
        int index=0;
        memset(v,0,sizeof(v));
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>num>>denomination;//种类和面值
            //接着将种类进行拆分
            int k=1;
            while(num-k>0){
                num-=k;
                v[++index]=k*denomination;
                //w[i]=k*? 因为这里没有类似质量的变量，所以不需要这一步啦
                k*=2; 
            } 
            v[++index]=num*denomination;
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=index;i++)
            for(int j=cash;j>=v[i];j--){//可以试一下不倒过来的 
                dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
            }
        int ans=0;
        for(int i=0;i<=cash;i++)
            ans=max(ans,dp[i]); 
        cout<<ans<<endl;
    }
    return 0;
}

Dividing

原本交了代码却wa了，幸亏没有放弃自己的代码，最后发现是忘记将dp归零了（捂脸

//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
//#include <cstdlib>
#include <cstring>
using namespace std;
int dp[100001],n,m,v[101],w[101],num[100001],nv[101],nw[101];
int max(int x,int y){
    return x>y?x:y;
}
int main()
{
    int m=1;
    //freopen("data","r",stdin);
    while(cin>>w[1]>>w[2]>>w[3]>>w[4]>>w[5]>>w[6]){
        int sum=0,index=0;
        for(int i=1;i<=6;i++){
            int k=1;
            sum+=i*w[i];
            while(w[i]>k){
                nw[++index]=k*i;
                w[i]-=k;
                k*=2;       
            }
            nw[++index]=w[i]*i;
        }
        if(sum==0)
            return 0;
        cout<<"Collection #"<<m++<<":"<<endl;
        if(sum%2){
            cout<<"Can't be divided."<<endl<<endl;
        }else{
            memset(dp,0,sizeof(dp));
            sum/=2;
            for(int i=1;i<=index;i++){
                for(int j=sum;j>=nw[i];j--)
                    dp[j]=max(dp[j],dp[j-nw[i]]+nw[i]);
            }
            if(dp[sum]==sum)
                cout<<"Can be divided."<<endl<<endl;
            else
                cout<<"Can't be divided."<<endl<<endl; 
        }
    }
    return 0;
}