题目描述
相信大家都学过背包问题了吧，那么现在我就考大家一个问题。有n个物品，每个物品有它的重量w，价值v，现在有一个容量为W的背包，问你在不超过背包容量的情况下，能装下的物品的最大价值是多少。
T <= 100代表样例数 1 <= n <= 100 物品数 1 <= W <= 100000 背包的容量 1 <= wi <= 100000 每个物品的重量 对于每个i=2,3,…,N, w1 ≤ wi ≤ w1+3. 1 <= vi <= 100000 每个物品的价值 输入
输入格式：
T n W w1 v1 w2 v2 : wn vn
输出
输出占一行，代表最大能装下物品的价值。 样例输入
2 4 6 2 1 3 4 4 10 3 4 4 6 2 1 3 7 4 10 3 6 样例输出
11 13
不会写，看的题解然后才写出来。 因为 cost 最多在四个层次，我们可以暴力（不过姿势不优雅也过不去） 代码
#include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 100+10; const int MAXM = 1e5; int a[MAXN],b[MAXN],c[MAXN],d[MAXN]; int aa[MAXN],bb[MAXN],cc[MAXN],dd[MAXN]; map<int,int>mp; bool cmp(int a,int b) { return a>b; } int main(){ int t;cin>>t; while(t--){ int n,v;mp.clear(); scanf("%d%d",&n,&v);int siz=0; int asiz,bsiz,csiz,dsiz; asiz=bsiz=csiz=dsiz=0; int num[5]; memset(num,0,sizeof(num)); for(int i=1;i<=n;++i){ int cost,val; scanf("%d%d",&cost,&val); if(mp[cost]==0) { mp[cost]=++siz; num[siz]=cost; } if(mp[cost]==1) a[++asiz]=val; else if(mp[cost]==2) b[++bsiz]=val; else if(mp[cost]==3) c[++csiz]=val; else d[++dsiz]=val; } // puts("==========="); a[0]=num[1];b[0]=num[2];c[0]=num[3];d[0]=num[4]; // for(int i=1;i<=4;i++) printf("%d ",num[i]); sort(a+1,a+1+asiz,cmp); // 排序很有必要，仔细想想就明白了 sort(b+1,b+1+bsiz,cmp); sort(c+1,c+1+csiz,cmp); sort(d+1,d+1+dsiz,cmp); // puts("===========");// 这里打的前缀表，因为后面要用到前几个物品要用多少钱 aa[1]=a[1];bb[1]=b[1];cc[1]=c[1];dd[1]=d[1]; for(int i=2;i<=asiz;i++) aa[i]=aa[i-1]+a[i]; for(int i=2;i<=bsiz;i++) bb[i]=bb[i-1]+b[i]; for(int i=2;i<=csiz;i++) cc[i]=cc[i-1]+c[i]; for(int i=2;i<=dsiz;i++) dd[i]=dd[i-1]+d[i]; int maxval=-1; for(int i=0;i<=asiz;i++){ for(int j=0;j<=bsiz;j++){ for(int k=0;k<=csiz;k++){ for(int l=0;l<=dsiz;l++){ if(i*a[0]+j*b[0]+k*c[0]+l*d[0]<=v){ // puts("==========="); maxval=max(aa[i]+bb[j]+cc[k]+dd[l],maxval); } } } } } printf("%d\n",maxval); } return 0; }