2019-03-19 分组背包问题

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int m,n,a[N],b[N],c[N],dp[N];
void qsort(int L,int R)
{
    int i=L,j=R,mid;
    while(i<=j)
    {
        mid=c[(i+j)/2];
        while(c[i]<mid) i++;
        while(c[j]>mid) j--;
        if(i<=j) 
        {
            swap(a[i],a[j]);
            swap(b[i],b[j]);
            swap(c[i],c[j]);
            i++;j--;
        }
    }
    if(L<j) qsort(L,j);
    if(i<R) qsort(i,R);
}
int main(void)
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
    }
    qsort(1,n);
    /* 
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
     cout<<endl;
    for(int i=1;i<=n;i++) cout<<b[i]<<" ";
     cout<<endl;
    for(int i=1;i<=n;i++) cout<<c[i]<<" ";
     cout<<endl;
    */ 
    int group=0;
    for(int i=1;i<=n;i++)
    {
        if(i==1 || (i!=1 && c[i]!=c[i-1])) group++;
    }
    int cnt=1;
    for(int k=1;k<=group;k++)
    {
        for(int v=m;v>=0;v--)
        {
            int first = true;
            for(; cnt!=n+1 && ( first || c[cnt]==c[cnt-1]) ;cnt++)
            {
                first=false;
                if(v-a[cnt]>=0) dp[v]=max(dp[v],dp[v-a[cnt]]+b[cnt]);
            } 
        }
    }
    //for(int i=1;i<=m;i++) cout<<dp[i]<<" ";
    cout<<dp[m]; 
    return 0;
} 





#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int m,n;
typedef struct node{
    long long  a,b,c; 
}Node;
Node p[N];
long long num[N],cnt,dp[N];
int cmp(Node p1,Node p2)
{
    return p1.c<p2.c;
}
int main(void)
{
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>p[i].a>>p[i].b>>p[i].c;
    sort(p+1,p+n+1,cmp);
    num[++cnt]=1;
    for(int i=2;i<=n;i++)
    {
        if(p[i].c==p[i-1].c) num[cnt]++;
        else num[++cnt]=1;  
    } 
    int sum=0;
    for(int k=1;k<=cnt;k++)
    {
        for(int v=m;v>=0;v--)
        {
            for(int j=sum+1;j<=sum+num[k];j++)
            {
                if(v>=p[j].a) dp[v]=max(dp[v],dp[v-p[j].a]+p[j].b);
            }
            sum+=num[k];
        }
    }
    cout<<dp[m];
    return 0;
} 






#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int M=1010,N=1010;
int m,n;
int f[M],a[N],b[N],c[101][20],cc[101],cn;
int main(void)
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        int C;
        cin>>a[i]>>b[i]>>C;
        cn=max(cn,C);
        cc[C]++;
        c[C][cc[C]]=i;
    }
    for(int i=1;i<=cn;i++)
    {
        for(int j=m;j>=0;j--)
        {
            for(int k=1;k<=cc[i];k++)
            if(j>=a[c[i][k]]) f[j]=max(f[j],f[j-a[c[i][k]]]+b[c[i][k]]);
        } 
    }   
    printf("%d",f[m]);  
    return 0;
}