01背包们 – Xhesica's blog

01背包，是一个非常基础的东西

在此列出三种基本操作

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int f[10000][10000];
 5 int v[100000];
 6 int t[100000];
 7 int n;
 8 int T;
 9 int main(){
10     cin>>T>>n;
11     for(int i=1;i<=n;++i)
12         scanf("%d%d",&t[i],&v[i]);
13     for(int i=1;i<=n;++i)
14         for(int j=T;j>=0;--j){
15             if(j>=t[i])
16                 f[i][j]=max(f[i-1][j-t[i]]+v[i],f[i-1][j]);
17                 else
18                 f[i][j]=f[i-1][j];
19         }
20         cout<<f[n][T];
21     return 0;
22 }
23

二维背包

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int f[10000];
 5 int v[100000];
 6 int t[100000];
 7 int n;
 8 int T;
 9 int main(){
10     cin>>T>>n;
11     for(int i=1;i<=n;++i)
12         scanf("%d%d",&t[i],&v[i]);
13     for(int i=1;i<=n;++i){
14         for(int j=T;j>=0;--j)
15             if(j>=t[i])
16                 {
17                     f[j]=max(f[j-t[i]]+v[i],f[j]);
18                 }
19     }
20     cout<<f[T];
21     return 0;
22 }

一维背包

 1     cin>>n>>m;
 2     for(int i=1;i<=n;++i){
 3         cin>>v[i];
 4     }
 5     g[0]=f[0]=1;
 6     for(int i=1;i<=n;++i)
 7         for(int j=m;j>=0;--j){
 8             if(j>=v[i])
 9             {
10                 f[j]+=f[j-v[i]];
11                 f[j]%=10;
12             }
13         }

求方案数

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论