【多校连萌2】A简单的背包问题【补题】

1279: 简单的背包问题

时间限制: 1 秒  内存限制: 32 MB 提交: 363  解决: 21 提交 状态 

题目描述

相信大家都学过背包问题了吧，那么现在我就考大家一个问题。有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 思路：看数据范围用普通的背包解法必定超范围，哪怕是longlong,题目给出了一个提示w1 ≤ wi ≤ w1+3.，   就可以把物体的重量分为四种情况，再将这四种情况的的价值分别按从大到小的顺序排列，枚举四种情况的物体数量情况，就可以得出给定容量下的最大价值

#include<stdio.h> #include<algorithm> using namespace std; #define N 110 long long v1[N],v2[N],v3[N],v4[N]; int cmp(int a,int b) { return a>b; } long long MAX(long long a,long long b) { if( a > b) return a; return b; } int main() { int t; int W,n; int w,w1,v; int a,b,c,d; int i,j,k,l; long long sum, ans; scanf("%d",&t); while(t --) { scanf("%d%d",&n,&W); a = b = c = d = 0; sum = 0; ans = 0; v1[a] = v2[b] = v3[c] = v4[d] = 0; scanf("%d%d",&w1,&v1[++a]); for(i = 2; i <= n; i ++) { scanf("%d%d",&w,&v); if(w == w1) v1[++a] = v; else if(w == w1+1) v2[++b] = v; else if(w == w1+2) v3[++c] = v; else if(w == w1+3) v4[++d] = v; } sort(v1+1,v1+a+1,cmp); sort(v2+1,v2+b+1,cmp); sort(v3+1,v3+c+1,cmp); sort(v4+1,v4+1+d,cmp); for(i = 2; i <= a; i ++) v1[i] += v1[i-1]; for(i = 2; i <= b; i ++) v2[i] += v2[i-1]; for(i = 2; i <= c; i ++) v3[i] += v3[i-1]; for(i = 2; i <= d; i ++) v4[i] += v4[i-1]; for(i = 0; i <=a; i ++) for(j = 0; j <= b; j ++) for(k = 0; k <= c; k ++) for(l = 0; l <= d; l ++) { sum = i*w1+j*(w1+1)+k*(w1+2)+l*(w1+3); if(sum <= W) { ans = MAX(ans,v1[i]+v2[j]+v3[k]+v4[l]); } } printf("%d\n",ans); } }