河南省多校联盟二-A

1279: 简单的背包问题

时间限制: 1 秒内存限制: 32 MB
提交: 361 解决: 20

题目描述

相信大家都学过背包问题了吧，那么现在我就考大家一个问题。有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

输出

输出占一行，代表最大能装下物品的价值。

样例输入

样例输出

11
13

由于BC卡的我到死，A题数据描述没仔细看，后来才发现只有四种不同的重量的物品。
剩下的无非是对于从四种不同重量的物品中每样挑出若干件的排列组合，四重for循环即可，由于使得价值最大化，所以每次都将优先选出当前重量级物品中的价值最大的几件，预处理一下前缀和即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool cmp(int a,int b){return a>b;}
 4 int main()
 5 {
 6     //freopen("in.txt","r",stdin);
 7     int dp[4][444];
 8     int W,n,w,i,t,j,p,k,s;
 9     cin>>t;
10     while(t--){int a=0,b=0,c=0,d=0,wi,vi;
11     dp[0][0]=dp[1][0]=dp[2][0]=dp[3][0]=0;
12         cin>>n>>W;
13         scanf("%d%d",&w,&vi);
14         dp[0][++a]=vi;
15         for(i=2;i<=n;++i){
16             scanf("%d%d",&wi,&vi);
17             if(wi==w){
18                 dp[0][++a]=vi;
19             }
20             else if(wi==w+1){
21                 dp[1][++b]=vi;
22             }
23             else if(wi==w+2){
24             }
25             else if(wi==w+3){
26                 dp[3][++d]=vi;
27             }
28         }
29         sort(dp[0]+1,dp[0]+1+a,cmp);
30         sort(dp[1]+1,dp[1]+1+b,cmp);
31         sort(dp[2]+1,dp[2]+1+c,cmp);
32         sort(dp[3]+1,dp[3]+1+d,cmp);
33         for(i=1;i<=a;++i) dp[0][i]+=dp[0][i-1];
34         for(i=1;i<=b;++i) dp[1][i]+=dp[1][i-1];
35         for(i=1;i<=c;++i) dp[2][i]+=dp[2][i-1];
36         for(i=1;i<=d;++i) dp[3][i]+=dp[3][i-1];
37         int ans=0;
38         for(i=0;i<=a;++i)
39             for(j=0;j<=b;++j)
40                for(k=0;k<=c;++k)
41                   for(p=0;p<=d;++p)
42         if((i+j+k+p)*w+j+2*k+3*p<=W)
43             ans=max(ans,dp[0][i]+dp[1][j]+dp[2][k]+dp[3][p]);
44         cout<<ans<<endl;
45     }
46     return 0;
47 }