【luogu1048】采药 [动规/01背包]

采药

杂是一个裸的01背包

f[v]表示不超过v的时间时最大价值

 1 /*
 2 id:gww
 3 language:
 4 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 
 5 */
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 const int N=100+10;
 9 int t,n,k[N],v[N],f[1000+10];
10 int rd()
11 {
12     int x=0,w=0;char ch=0;
13     while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
14     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
15     return w?-x:x;
16 }
17 
18 int main()
19 {
20     t=rd(),n=rd();
21     for(int i=1;i<=n;i++)
22     v[i]=rd(),k[i]=rd();
23     for(int i=1;i<=n;i++)
24     for(int j=t;j>=v[i];j--)
25     f[j]=max(f[j-v[i]]+k[i],f[j]);
26     printf("%d",f[t]);
27     return 0;
28 }

一维数组

f[i][j]表示前i个草药在时间j之前的最大价值

 1 /*
 2 id:gww
 3 language:
 4 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊 
 5 */
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 const int N=100+10;
 9 int t,n,k[N],v[N],f[N][1000+10];
10 int rd()
11 {
12     int x=0,w=0;char ch=0;
13     while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
14     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
15     return w?-x:x;
16 }
17 
18 int main()
19 {
20     t=rd(),n=rd();
21     for(int i=1;i<=n;i++)
22     v[i]=rd(),k[i]=rd();
23     for(int i=1;i<=n;i++)//枚举个数
24     for(int j=t;j>=0;j--)
25     {
26         if(j>=v[i])//放得下 
27         f[i][j]=max(f[i-1][j-v[i]]+k[i],f[i-1][j]);
28         else//放不下 
29         f[i][j]=f[i-1][j];
30     }
31     printf("%d",f[n][t]);
32     return 0;
33 }

二维