背包问题

二进制多重背包问题：

仔细看代码

#include <bits/stdc++.h>
using namespace std;
#define ri register int 
#define M 10005

struct dian{
    int val,v;
}p[M];

int n,m;
int dis[M];
int trmp;
int main(){
    scanf("%d%d",&n,&m);
    for(ri i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        for(int j=1;j<=c;j<<=1)   // 
        {
            p[++cent].v=a*j;
            p[cent].val=b*j;
            c-=j;
        }
        if(c) p[++cent].v=c*a,p[cent].val=c*b; // 这个c作为分界点，前后都可以表示出来 
    }
    
    for(ri i=1;i<=cent;i++)
    for(ri j=m;j>=p[i].val;j++)
    {
        dis[j]=max(dis[j-p[i].v]+p[i].val,dis[v]);
    }
    printf("%d",dis[m]);
    
}

View Code

分组背包的

就对与每一个 v 分组挑选一个最好的

#include <bits/stdc++.h>
using namespace std;
#define ri register int 
#define M 1005

vector <int> q[11];
struct dain{
    int val,v;
}p[M];
int n,m,T;
int dis[M];
int mx(int v,int t)
{
    int maxx=dis[v];
    for(ri i=0;i<q[t].size();i++)
    {
        int b=q[t][i];
        if(v-p[b].v>=0)
        {
            maxx=max(maxx,dis[v-p[b].v]+p[b].val);
        }
    }
    return maxx;
}
int main(){
    
    scanf("%d%d%d",&m,&n,&T);
    
    for(ri i=1;i<=n;i++)
    {
        int t;
        scanf("%d%d%d",&p[i].v,&p[i].val,&t);
        q[t].push_back(i);
    }
    for(ri i=1;i<=T;i++) //
    for(ri j=m;j>=1;j--)
    {
        dis[j]=mx(j,i);
    }
    printf("%d",dis[m]);
    return 0;
}

View Code

无限背包问题：

顺序 1--m

01背包问题

逆序m--1