背包dp总结 ###K

背包问题总结

当空间优化为一维后的限制

除了完全背包和多重背包的单调队列优化写法其他的背包问题体积都是从大到小循环的

体积至多为v 一般的背包问题

体积恰好为v 除了dp[0]外其他初始化为无穷即可

体积至少为v 除了dp[0]外其他初始化为无穷更新的时候 j-w[i] 可以是负数也可以是正数

写的时候写成 max(0,j-w[i]) 即可因为dp[5]可以由dp[5-8]更新而来，因为8就满足至少是5

//当然也有把空间开得很大的笨比做法

背包的至少问题

题目链接：https://www.acwing.com/problem/content/1022/

题目链接：https://www.luogu.com.cn/problem/P2918

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=1e8;
 5 #define ll long long
 6 #define pb push_back
 7 int dp[maxn][maxn];
 8 
 9 
10 int main()
11 {
12     ios::sync_with_stdio(0);
13     cin.tie(0);
14     memset(dp,0x3f,sizeof(dp));
15     dp[0][0]=0;
16     int m,n,k;
17     cin>>m>>n>>k;
18     for(int i=1;i<=k;i++)
19     {
20         int a,b,c;
21         cin>>a>>b>>c;
22         for(int j=m;j>=0;j--)
23             for(int k=n;k>=0;k--)
24                 dp[j][k]=min(dp[j][k],dp[max(0,j-a)][max(0,k-b)]+c);
25     }
26     cout<'\n';
27 
28 
29 
30 
31 
32 }

 1 #include
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e8;
 5 #define ll long long
 6 #define pb push_back
 7 int dp[maxn];
 8 
 9 
10 int main()
11 {
12     ios::sync_with_stdio(0);
13     cin.tie(0);
14     int n,h;
15     cin>>n>>h;
16     memset(dp,0x3f,sizeof(dp));
17     dp[0]=0;
18     for(int i=1;i<=n;i++)
19     {
20         int p,c;
21         cin>>p>>c;
22         for(int j=0;j<=h;j++)
23             dp[j]=min(dp[j],dp[max(0,j-p)]+c);
24     }
25     cout<'\n';
26 
27 
28 
29 
30 
31 
32 }

分别是二维的01背包至少问题和一维的完全背包至少问题

01背包求方案数问题

完全背包求方案数问题

题目链接：https://www.acwing.com/problem/content/280/

题目链接：https://www.acwing.com/problem/content/1025/

 1 #include
 2 using namespace std;
 3 const int maxn=1e4+10;
 4 const int mod=1e8;
 5 #define ll long long
 6 #define pb push_back
 7 int dp[maxn];
 8 
 9 
10 int main()
11 {
12     ios::sync_with_stdio(0);
13     cin.tie(0);
14     int n,m;
15     cin>>n>>m;
16     dp[0]=1;
17     for(int i=1;i<=n;i++)
18     {
19         int x;
20         cin>>x;
21         for(int j=m;j>=x;j--)
22             dp[j]+=dp[j-x];
23     }
24     cout<'\n';
25     
26     
27     
28 
29 
30 
31 
32 
33 }

只需要初始化dp[0]=1 即没有选择物品的时候体积为0是一种合法方案，数字M为背包容量，每个数为所占的体积

那么dp[i][j]= dpi-1[[j]+dp[i-1][j-v] 每个状态等于选和不选的方案数

 1 #include
 2 using namespace std;
 3 const int maxn=1e3+10;
 4 const int mod=1e8;
 5 #define ll long long
 6 #define pb push_back
 7 int dp[maxn];
 8 int a[5]={58,10,20,50,100};
 9 
10 
11 int main()
12 {
13     ios::sync_with_stdio(0);
14     cin.tie(0);
15     int n;
16     cin>>n;
17     dp[0]=1;
18     for(int i=1;i<=4;i++)
19     {
20         int w=a[i];
21         for(int j=w;j<=n;j++)
22             dp[j]+=dp[j-w];
23     }
24     cout<'\n';
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 }

注意背包求出的方案数是无序的，和那些在后面接数的一般dp不同那些是有序的

多重背包的三种解法

1.暴力循环 2.二进制优化 3.单调队列优化

题目链接：https://www.acwing.com/problem/content/1021/

题目链接：https://www.acwing.com/problem/content/5/ 二进制优化后 temp中的数量为nlogn个总的时间复杂度 nlogn*V

题目链接：https://www.acwing.com/problem/content/description/6/ 单调队列优化时间复杂度o(n*V) 但是完全没理解只能当模板用

 1 #include
 2 using namespace std;
 3 const int maxn=6e3+10;
 4 const int mod=1e8;
 5 #define ll long long
 6 #define pb push_back
 7 int dp[maxn];
 8 
 9 
10 int main()
11 {
12     ios::sync_with_stdio(0);
13     cin.tie(0);
14     int n,m;
15     cin>>n>>m;
16     for(int i=1;i<=n;i++)
17     {
18         int v,w,s;
19         cin>>v>>w>>s;
20         for(int j=m;j>=v;j--)
21             for(int k=1;k<=s;k++)
22                 if(j>=k*v)
23                     dp[j]=max(dp[j],dp[j-k*v]+k*w);
24     }
25     cout<'\n';
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 }

 1 #include
 2 using namespace std;
 3 const int maxn=2e3+10;
 4 const int mod=1e8;
 5 #define ll long long
 6 #define pb push_back
 7 int dp[maxn];
 8 
 9 struct ac
10 {
11     int v,w;
12 };
13 
14 
15 
16 int main()
17 {
18     ios::sync_with_stdio(0);
19     cin.tie(0);
20     int n,V;
21     cin>>n>>V;
22     vectortemp;
23     for(int i=1;i<=n;i++)
24     {
25         int v,w,s;
26         cin>>v>>w>>s;
27         for(int k=1;k<=s;k*=2)
28         {
29             s-=k;
30             temp.pb({v*k,w*k});
31         }
32         if(s)
33         temp.pb({v*s,w*s});
34     }
35 
36     for(auto &v:temp)
37         for(int j=V;j>=v.v;j--)
38             dp[j]=max(dp[j],dp[j-v.v]+v.w);
39 
40     cout<'\n';
41 
42 
43 
44 
45 }

 1 #include
 2 using namespace std;
 3 const int maxn=2e4+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define fi first
 8 #define sc second
 9 
10 int n,m;
11 int f[maxn],g[maxn],q[maxn];
12 
13 
14 
15 
16 int main()
17 {
18     ios::sync_with_stdio(0);
19     cin.tie(0);
20     cin>>n>>m;// 物品数和背包体积
21     for(int i=0;i)
22     {
23         int v,w,s;// 体积 价值 数量
24         cin>>v>>w>>s;
25         memcpy(g,f,sizeof(f));
26         for(int j=0;j// 枚举余数 即等价类
27         {
28             int hh=0,tt=-1;
29             for(int k=j;k<=m;k+=v)
30             {
31                 if(hh<=tt&&q[hh];
32                 if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
33                 while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w) tt--;
34                 q[++tt]=k;
35             }
36         }
37     }
38     cout<'\n';
39 
40 
41 
42 
43 
44 }

二进制优化是根据二进制的拆分使得剩下的组通过选和不选可以得到选所有数的方案数

比如 11拆分成 0001 0010 0100 0100 即 1 2 4 4 通过这四个数的选和不选可以得到 0~11 任意一种方案

那么即把0~11 拆分成了这4份数跑一遍01背包即可

背包问题求具体方案

题目链接：https://www.acwing.com/problem/content/12/

 1 #include
 2 using namespace std;
 3 const int maxn=1e3+10;
 4 const int mod=1e8;
 5 #define ll long long
 6 #define pb push_back
 7 #define fi first
 8 #define sc second
 9 
10 int dp[maxn][maxn];
11 int v[maxn],w[maxn];
12 
13 
14 
15 int main()
16 {
17     ios::sync_with_stdio(0);
18     cin.tie(0);
19     int n,V;
20     cin>>n>>V;
21     for(int i=1;i<=n;i++)
22         cin>>v[i]>>w[i];
23 
24     for(int i=n;i>=1;i--)
25     {
26         for(int j=0;j<=V;j++)
27         {
28             dp[i][j]=dp[i+1][j];
29             if(j>=v[i])
30                 dp[i][j]=max(dp[i][j],dp[i+1][j-v[i]]+w[i]);
31         }
32     }
33 
34     vector<int>ans;
35     int k=V;
36     for(int i=1;i<=n;i++)
37     {
38         if(k-v[i]>=0&&dp[i][k]==dp[i+1][k-v[i]]+w[i])
39             ans.pb(i),k-=v[i];
40     }
41     int len=ans.size();
42     for(int i=0;i)
43     {
44         if(i!=0)
45             cout<<" ";
46         cout<<ans[i];
47     }
48     cout<<'\n';
49 
50 
51 
52 }

因为需要通过状态来往回找所以必须使用二维数组而不能滚动数组，然后题目要求字典序最小的话就倒着一遍01背包

然后从1开始有的选就选贪心使得字典序最小，用来判断当前这个物品取和不取是比较 dp[i-1][j-v[i]]+w[i] 是否等于dp[i][j]

因为每个状态由 dp[i-1][j] 和dp[i-1][j-v[i]]+w[i] 两个状态转移过来，和谁的值相同就代表和谁转移过来

关于具体方案第二种做法是开多一个数组g[i][j] 来记录取和没取

 1 #include
 2 using namespace std;
 3 const int maxn=1e3+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 
12 int dp[maxn][maxn];
13 int v[maxn],w[maxn];
14 int g[maxn][maxn];
15 
16 
17 int main()
18 {
19     ios::sync_with_stdio(false);
20     cin.tie(0);
21     int n,V;
22     cin>>n>>V;
23     for(int i=n;i>=1;i--) cin>>v[i]>>w[i];
24     for(int i=1;i<=n;i++)
25     {
26         for(int j=0;j<=V;j++)
27         {
28             dp[i][j]=dp[i-1][j];
29             if(j-v[i]>=0)
30             {
31                 int x=dp[i-1][j-v[i]]+w[i];
32                 if(x>=dp[i][j])
33                 {
34                     dp[i][j]=x;
35                     g[i][j]=1;
36                 }
37             }
38         }
39     }
40     int k=V;
41     vector<int>ans;
42     for(int i=n,j=1;i>=1;i--,j++)
43     {
44         if(g[i][k])
45         {
46             k-=v[i];
47             ans.pb(j);
48         }
49     }
50 
51     for(auto &c:ans) cout<" ";
52 
53 
54 
55 
56 
57 
58 
59 
60 }

分组背包问题

注意先枚举组数再枚举体积再枚举每组里面的物品即可

题目链接：https://www.acwing.com/problem/content/9/

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define fi first
 8 #define sc second
 9 vectorint,int>>E[maxn];
10 int dp[maxn];
11 int v[maxn],w[maxn];
12 
13 
14 
15 int main()
16 {
17     ios::sync_with_stdio(0);
18     cin.tie(0);
19     int n,V;
20     cin>>n>>V;
21     for(int i=1;i<=n;i++)
22     {
23         int s;
24         cin>>s;
25         for(int j=1;j<=s;j++)
26             cin>>v[j]>>w[j];
27         for(int j=V;j>=0;j--)
28         {
29             for(int k=1;k<=s;k++)
30             {
31                 if(j>=v[k])
32                     dp[j]=max(dp[j],dp[j-v[k]]+w[k]);
33             }
34         }
35     }
36     cout<'\n';
37 
38 
39 
40 
41 
42 
43 
44 }

题目传送门：https://www.cnblogs.com/winfor/p/14027812.html

题目链接：https://www.acwing.com/problem/content/489/

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define fi first
 8 #define sc second
 9 
10 struct ac
11 {
12     int v,p;
13 };
14 ac z[maxn];
15 int dp[100010];
16 
17 vectorf[maxn];
18 
19 
20 int main()
21 {
22     ios::sync_with_stdio(0);
23     cin.tie(0);
24     int V,n;
25     cin>>V>>n;
26     for(int i=1;i<=n;i++)
27     {
28         int v,p,q;
29         cin>>v>>p>>q;
30         p*=v;
31         if(!q)z[i]={v,p};
32         else f[q].pb({v,p});
33     }
34     for(int i=1;i<=n;i++)
35     {
36         for(int j=V;j>=0;j--)
37         {
38             int num=f[i].size();
39             for(int k=0;k<(1<)
40             {
41                 int v=z[i].v,w=z[i].p;
42                 for(int y=0;y)
43                 {
44                     if((k>>y)&1)
45                         v+=f[i][y].v,w+=f[i][y].p;
46                 }
47                 if(j>=v)
48                     dp[j]=max(dp[j],dp[j-v]+w);
49             }
50         }
51     }
52     cout<'\n';
53 
54 
55 
56 
57 }

可以把每组分成附件取和不取的情况，因为最多有两种情况，所以最多有4种情况，用二进制枚举可以简便写代码

混合背包问题

只是判断当前的用哪一种类型的背包直接套01和完全或者多重背包即可

题目链接：https://www.acwing.com/problem/content/7/

 1 #include
 2 using namespace std;
 3 const int maxn=1e3+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define fi first
 8 #define sc second
 9 int dp[maxn];
10 struct ac
11 {
12     int v,w;
13 };
14 
15 
16 
17 
18 int main()
19 {
20     ios::sync_with_stdio(0);
21     cin.tie(0);
22     int n,V;
23     cin>>n>>V;
24     for(int i=1;i<=n;i++)
25     {
26         int v,w,s;
27         cin>>v>>w>>s;
28         if(s==-1)
29         {
30             for(int j=V;j>=v;j--)
31                 dp[j]=max(dp[j],dp[j-v]+w);
32         }
33         else if(s==0)
34         {
35             for(int j=v;j<=V;j++)
36                 dp[j]=max(dp[j],dp[j-v]+w);
37         }
38         else
39         {
40             vectortemp;
41             for(int j=1;j<=s;j*=2)
42             {
43                 temp.pb({j*v,j*w});
44                 s-=j;
45             }
46             if(s)
47                 temp.pb({s*v,s*w});
48             for(auto &v:temp)
49                 for(int j=V;j>=v.v;j--)
50                     dp[j]=max(dp[j],dp[j-v.v]+v.w);
51         }
52     }
53     cout<'\n';
54 
55 
56 
57 
58 
59 }

有依赖的的背包问题树形背包时间复杂度 o(n^3)

树形dp＋分组背包有两种写法，一种是dp[u][j] 是包括根为u的选法，另外一种写法是dp[u][j] 是不包含根的

第二种写法不需要确保把当前的点在放入dp[u][j]中，也不需要清空不符合条件的情况但是需要弄一个虚的根节点

并且需要在 for 子树中的时候拿到子树的点

选择第一种的话一定记得清空非法情况即可

所以在权值在边上的情况下必选第二种权值在点上的选第一种更好, 当然也要视情况而定

题目链接：https://www.acwing.com/activity/content/problem/content/1281/1/

 1 #include
 2 using namespace std;
 3 const int maxn=3e2+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 
11 int n,V;
12 vector<int>E[maxn];
13 int v[maxn],w[maxn];
14 int dp[maxn][maxn];
15 
16 void dfs(int u)
17 {
18     for(auto &v:E[u])
19     {
20         dfs(v);
21         for(int j=V;j>=0;j--)
22             for(int k=0;k<=j;k++)
23                 dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
24     }
25     for(int i=V;i>=0;i--)
26     {
27         if(i>=v[u])
28             dp[u][i]=dp[u][i-v[u]]+w[u];
29         else
30             dp[u][i]=0;
31     }
32 }
33 
34 
35 
36 int main()
37 {
38     ios::sync_with_stdio(0);
39     cin.tie(0);
40     cin>>n>>V;
41     int rt=0;
42     for(int i=1;i<=n;i++)
43     {
44         int p;
45         cin>>v[i]>>w[i]>>p;
46         if(p==-1)
47             rt=i;
48         else
49             E[p].pb(i);
50     }
51     dfs(rt);
52     cout<'\n';
53 
54 
55 
56 
57 }

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define fi first
 8 #define sc second
 9 
10 int n,V;
11 int dp[maxn][maxn];
12 int v[maxn],w[maxn];
13 vector<int>E[maxn];
14 
15 
16 void dfs(int u)
17 {
18     for(auto &s:E[u])// 每棵子树为一个物品组
19     {
20         dfs(s);
21         for(int j=V;j>=v[s];j--) // 枚举体积
22             for(int k=0;k<=j-v[s];k++)  // 枚举决策
23                 dp[u][j]=max(dp[u][j],dp[u][j-k-v[s]]+dp[s][k]+w[s]);
24     }
25 
26 }
27 
28 
29 int main()
30 {
31     ios::sync_with_stdio(0);
32     cin.tie(0);
33     cin>>n>>V;
34     int rt=0;
35     for(int i=1;i<=n;i++)
36     {
37         int p;
38         cin>>v[i]>>w[i]>>p;
39         if(p==-1)
40             rt=i;
41         else
42             E[p].pb(i);
43     }
44     E[0].pb(rt);
45     dfs(0);
46     //cout<
47     cout<0][V]<<'\n';
48 
49 
50 
51 
52 
53 }

二叉苹果树传送门：https://www.cnblogs.com/winfor/p/14033652.html

 1 #include
 2 using namespace std;
 3 const int maxn=1e2+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 
11 int n,V;
12 int dp[maxn][maxn];
13 vectorE[maxn];
14 
15 void dfs(int u,int fa)
16 {
17     for(auto &v:E[u])
18     {
19         if(v.fi==fa)
20             continue;
21         dfs(v.fi,u);
22         for(int j=V;j>=0;j--)
23             for(int k=0;k<=j-1;k++)
24                 dp[u][j]=max(dp[u][j],dp[v.fi][k]+dp[u][j-k-1]+v.sc);
25 
26     }
27 
28 }
29 
30 
31 int main()
32 {
33     ios::sync_with_stdio(0);
34     cin.tie(0);
35     cin>>n>>V;
36     for(int i=1;i)
37     {
38         int x,y,z;
39         cin>>x>>y>>z;
40         E[x].pb({y,z});
41         E[y].pb({x,z});
42     }
43     dfs(1,0);
44     cout<1][V]<<'\n';
45 
46 
47 
48 
49 }

求最优解的所有方案数 //还需思考

题目链接：https://www.acwing.com/problem/content/11/

g[i][j] 表示的是f[i][j] 状态下取得最大值的方案数

可以优化成一维 g[j] 全部初始化为1 因为刚开始空的时候最大值是0 即什么都不放，

此时 g[j] 的方案就为1

 1 #include
 2 using namespace std;
 3 const int maxn=1e3+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define pb push_back
 7 #define pi pair
 8 #define fi first
 9 #define sc second
10 
11 int g[maxn],dp[maxn];
12 
13 
14 
15 int main()
16 {
17     ios::sync_with_stdio(0);
18     cin.tie(0);
19     int n,V;
20     cin>>n>>V;
21     for(int i=0;i<=V;i++) g[i]=1;
22     for(int i=1;i<=n;i++)
23     {
24         int v,w;
25         cin>>v>>w;
26         for(int j=V;j>=v;j--)
27         {
28             int max1=max(dp[j],dp[j-v]+w);
29             int cnt=0;
30             if(max1==dp[j])
31                 cnt+=g[j],cnt%=mod;
32             if(max1==dp[j-v]+w)
33                 cnt+=g[j-v],cnt%=mod;
34             g[j]=cnt;
35             dp[j]=max1;
36         }
37     }
38     cout<'\n';
39 
40 
41 
42 }

贪心+01背包能量石 ###K //K

题目链接：https://www.acwing.com/problem/content/description/736/

 1 #include
 2 using namespace std;
 3 const int maxn=1e4+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define pb push_back
 7 #define fi first
 8 #define sc second
 9 
10 int dp[maxn];
11 struct ac
12 {
13     int s,e,l;
14     bool operator<(ac a)
15     {
16         return s*a.ll;
17     }
18 };
19 ac a[150];
20 
21 
22 
23 int main()
24 {
25     ios::sync_with_stdio(0);
26     cin.tie(0);
27     int t;
28     cin>>t;
29     int cnt=0;
30     while(t--)
31     {
32         int n;
33         cin>>n;
34         int V=1e4;
35         memset(dp,-0x3f,sizeof(dp));
36         dp[0]=0;
37         for(int i=1;i<=n;i++)
38         {
39             int s,e,l;
40             cin>>s>>e>>l;
41             a[i]={s,e,l};
42         }
43         sort(a+1,a+1+n);
44         for(int i=1;i<=n;i++)
45         {
46             int s=a[i].s,e=a[i].e,l=a[i].l;
47             for(int j=V;j>=s;j--)
48             {
49                 dp[j]=max(dp[j],dp[j-s]+e-l*(j-s));
50             }
51         }
52         int ans=0;
53         for(int i=1;i<=V;i++)
54             ans=max(ans,dp[i]);
55         cout<<"Case #"<<++cnt<<": "<'\n';
56     }
57 
58 
59 
60 
61 }

考虑直接01背包也就是每个物品选和不选，但是发现选择的顺序会影响结果，所以我们需要贪心

而dp 都是按照顺序来进行选择有顺序影响的话dp就不能保证准确所以必须要把选择的方案变成无序再dp

假设第i个和第i+1个谁先选的问题，那么先选第i个再第i+1个的值 ei + e(i+1) - si*(l(i+1))

而先选i+1个再选第i个的值为 ei + e(i+1) -s(i+1)*(li) 最终贪心得到一定按照 si*(l(i+1))

然后就把问题变成了没有顺序的问题，按照这个顺序直接01背包即可需要注意的是这里的时间根据实际含义所以

我们发现这里应该将dp[i] 定义为时间恰好为i 更好因为随着时间的上升并不一定会使得答案更大

背包DP B总结

背包dp总结 ###K

相关

标签