5483: 神奇的背包(带有限制的01背包)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,m,t,maxx;
 5 int dp[1005],dpp[1005];
 6 struct Node{
 7     int w,v;
 8 }A[1005];
 9 
10 bool cmp(Node a,Node b){
11     if(a.v!=b.v) return a.v>b.v;   //先按照价值排序
12     return a.w>b.w;  //在按照重量
13 }
14 
15 int main()
16 {
17     ios::sync_with_stdio(false);
18     cin>>n>>m>>t;
19     for(int i=1,d1,d2;i<=t;i++){
20         cin>>d1>>d2;
21         A[i]={d1,d2};
22     }
23     sort(A+1,A+1+t,cmp);
24     for(int i=1;i<=t;i++){
25         if(i!=1){
26             for(int k=n-m;k>=A[i].w;k--){   //预存出m的空间  拿来放最大的价值
27                 dpp[k]=max(dpp[k],dpp[k-A[i].w]+A[i].v);
28             }
29         }
30         for(int k=n;k>=A[i].w;k--){
31             dp[k]=max(dp[k],dp[k-A[i].w]+A[i].v);
32         }
33     }
34     for(int i=1;i<=n-m;i++) dpp[i]+=A[1].v;  //放入
35     int res=0;
36     for(int i=1;i<=n;i++){
37         int maxx;
38         maxx=max(dp[i],dpp[i]);  //两者进行比较
39         res=max(res,maxx);
40     }
41     cout << res << endl;
42     return 0;
43 }