首页 > 编程札记 > 编程

背包问题至多，至少，恰好问题的研究

阅读：评论：0

背包问题至多，至少，恰好问题的研究

写在开头：
本文参考：/
仅作为笔记使用

Ⅰ. 结论

一. 求方案数初始化总结

1. 二维情况

体积至多是j，f[0][i]=1,0<=i<=m，其余是0
体积恰好是j，f[0][0]=1，其余是0
体积至少j，f[0][0]=1,其余是0

2. 一维情况

体积至多j，f[i]=1，0<=i<=m
体积恰好j,f[0]=1，其余是0
体积至少j，f[0]=1,其余是0

求最大值和最小值初始化总结

1. 二维情况

体积至多是j，f[i,k]=0,0<=i<=m,0<=k<=m
体积恰好是j，
当前价值的最小值：f[0][0]=0，其余是INF
当求价值的最大值:f[0][0]=0，其余是-INF
体积至少j,f[0][0]=0，其余是INF （只会求价值最小值）

2. 一维情况

体积至多j，f[i]=0，0<=i<=m（只会求价值的最大值）
体积恰好j
当求价值的最小值：f[0]=0，其余是INF
当求价值的最大值:f[0]=0，其余是-INF
体积至少j，f[0]=0，其余是INF（只会求价值最小值）

Ⅱ . 具体问题

一. 求方案数问题

从前i个物品中选，总体积不超过j的总方案数,初始化f[0][i]=1，0<=i<=m其余是0
01背包
每个物品有一定的体积，只能选一次，求总体积不超过m的方案数
二维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int n, m;
int main()
{cin >> n >> m;for (int i = 0; i <= m; i++)f[0][i] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if (j >= v)f[i][j] += f[i - 1][j - v];}}cout << f[n][m] << endl;return 0;
}

一维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N];
int n, m;
int main()
{cin >> n >> m;for (int i = 0; i <= m; i++)f[i] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = m; j >= v; j--)f[j] += f[j - v];}cout << f[m] << endl;return 0;
}

完全背包
给你一堆物品，每个物品有一定的体积，每个物品可以选无数多个，总体积不超过m的方案数
二维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int f[N][N];
int main()
{cin >> n >> m;for (int i = 0; i <= m; i++) f[0][i] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if (j >= v) f[i][j] += f[i][j - v];}}cout << f[n][m] << endl;return 0;
}

一维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int f[N];
int main()
{cin >> n >> m;for (int i = 0; i <= m; i++) f[i] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = v; j <= m; j++)f[j] += f[j - v];}cout << f[m] << endl;return 0;
}

从前 i 个物品中选，且总体积恰好是j的方案数,初始化为f[0][0]=1其余是0

01背包
给你一堆物品，每个物品有一定的体积，每个物品只能选一个，求总体积恰好是m的方案数
二维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int f[N][N];
int main()
{cin >> n >> m;f[0][0] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if (j >= v)f[i][j] += f[i - 1][j - v];}}cout << f[n][m] << endl;return 0;
}

一维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int f[N];
int main()
{cin >> n >> m;f[0] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = m; j >= v; j--){f[j] += f[j - v];}}cout << f[m] << endl;return 0;
}

完全背包
给你一堆物品，每个物品有一定的体积，每个物品可以选无数多个，求总体积恰好是m的方案数
二维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int f[N][N];
int main()
{cin >> n >> m;f[0][0] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if(j>=v)f[i][j] += f[i][j - v];}}cout << f[n][m] << endl;return 0;
}

一维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int f[N];
int main()
{cin >> n >> m;f[0] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = v; j <= m; j++){f[j] += f[j - v];}}cout << f[m] << endl;return 0;
}

从前i个物品中选，总体积至少是j的总方案数，初始化f[0][0]=1,其余至少是0,至少的情况，j需要从0枚举到m，或者从m枚举到0）
01背包
给你一堆物品，每个物品有一定的体积，每个物品只能选一个，求总体积至少是m的方案数

#include <iostream>using namespace std;const int N = 110;int n, m;
int f[N][N];int main()
{cin >> n >> m;f[0][0] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = 0; j <= m; j++)//即使物品体积比j大，j - v < 0，也能选，等价于f[i - 1][0]{f[i][j] = f[i - 1][j] + f[i - 1][max(0, j - v)];}}cout << f[n][m] << endl;return 0;
}

一维code

#include <iostream>using namespace std;const int N = 110;int n, m;
int f[N];int main()
{cin >> n >> m;f[0] = 1;for (int i = 1; i <= n; i++){int v;cin >> v;for (int j = m; j >= 0; j--)//即使物品体积比j大，j - v < 0，也能选，等价于f[i - 1][0]{f[j] += f[max(0, j - v)];}}cout << f[m] << endl;return 0;
}

二. 求最大值最小值问题

从前i个物品中选，且总体积不超过j的最大价值，初始化是f[i,k] = 0，0 <= i <= n, 0 <= k <= m（只会求价值的最大值）

01背包问题
给你一堆物品，每个物品有一定的体积和对应的价值，每个物品只能选一个，求总体积不超过m的最大价值
二维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int n, m;
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){int w, v;cin >> v >> w;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if (j >= v)f[i][j] = max(f[i][j], f[i - 1][j - v] + w);}}cout << f[n][m] << endl;return 0;
}

一维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N];
int n, m;
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){int w, v;cin >> v >> w;for (int j = m; j >= v; j--){f[j] = max(f[j], f[j - v] + w);}}cout << f[m] << endl;return 0;
}

从前i个物品中选，且总体积恰好是j
求价值最小值：初始化f[0][0] = 0, 其余是INF
01背包
给你一堆物品，每个物品有一定的体积和对应的价值，每个物品只能选一个，求总体积恰好是j的最小价值
二维code

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int f[N][N];
int n, m;
int main()
{cin >> n >> m;memset(f, 0x3f, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++){int v, w;cin >> v >> w;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if (j >= v)f[i][j] = min(f[i][j], f[i - 1][j - v] + w);}}cout << f[n][m] << endl;return 0;
}

一维code

#include <bits/stdc++.h>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N];int main()
{cin >> n >> m;memset(f, INF, sizeof f);f[0] = 0;for(int i = 1;i <= n;i ++){int v, w;cin >> v >> w;for(int j = m;j >= v;j --){f[j] = min(f[j], f[j - v] + w);}}cout << f[m] << endl;return 0;
}

求价值最大值：初始化f[0][0] = 0, 其余是-INF
给你一堆物品，每个物品有一定的体积和对应的价值，每个物品只能选一个，求总体积恰好是j的最大价值
二维code

#include <bits/stdc++.h>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N][N];int main()
{cin >> n >> m;memset(f, -INF, sizeof f);f[0][0] = 0;for(int i = 1;i <= n;i ++){int v, w;cin >> v >> w;for(int j = 0;j <= m;j ++){f[i][j] = f[i - 1][j];if(j >= v) f[i][j] = max(f[i][j], f[i - 1][j - v] + w);}}cout << f[n][m] << endl;return 0;
}

一维code

#include <iostream>
#include <cstring>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N];int main()
{cin >> n >> m;memset(f, -INF, sizeof f);f[0] = 0;for(int i = 1;i <= n;i ++){int v, w;cin >> v >> w;for(int j = m;j >= v;j --){f[j] = max(f[j], f[j - v] + w);}}cout << f[m] << endl;return 0;
}

完全背包

求价值最小值：初始化f[0][0] = 0, 其余是INF
给你一堆物品，每个物品有一定的体积和对应的价值，每个物品可以选无数多个，求总体积恰好是j的最小价值

#include <bits/stdc++.h>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N][N];int main()
{cin >> n >> m;memset(f, INF, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++){int v, w;cin >> v >> w;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if (j >= v) f[i][j] = min(f[i][j], f[i][j - v] + w);}}cout << f[n][m] << endl;return 0;
}

一维code

#include <bits/stdc++.h>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N];int main()
{cin >> n >> m;memset(f, INF, sizeof f);f[0] = 0;for (int i = 1; i <= n; i++){int v, w;cin >> v >> w;for (int j = v; j <= m; j++){f[j] = min(f[j], f[j - v] + w);}}cout << f[m] << endl;return 0;
}

求价值最大值：初始化f[0][0] = 0, 其余是-INF
给你一堆物品，每个物品有一定的体积和对应的价值，每个物品可以选无数多个，求总体积恰好是j的最大价值
二维code

#include <iostream>
#include <cstring>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N][N];int main()
{cin >> n >> m;memset(f, -INF, sizeof f);f[0][0] = 0;for (int i = 1; i <= n; i++){int v, w;cin >> v >> w;for (int j = 0; j <= m; j++){f[i][j] = f[i - 1][j];if (j >= v) f[i][j] = max(f[i][j], f[i][j - v] + w);}}cout << f[n][m] << endl;return 0;
}

一维code

#include <iostream>
#include <cstring>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N];int main()
{cin >> n >> m;memset(f, -INF, sizeof f);f[0] = 0;for(int i = 1;i <= n;i ++){int v, w;cin >> v >> w;for(int j = v;j <= m;j ++){f[j] = max(f[j], f[j - v] + w);}}cout << f[m] << endl;return 0;
}

3、从前i个物品中选，且总体积至少是j，初始化是f[0][0] = 0, 其余是INF（只会求价值的最小值）

例子：给你一堆物品，每个物品有一定的体积和对应的价值，每个物品可以选无数多个，求总体积至少是j的最小价值
二维code

#include <iostream>
#include <cstring>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N][N];int main()
{cin >> n >> m;memset(f, INF, sizeof f);f[0][0] = 0;for(int i = 1;i <= n;i ++){int v, w;cin >> v >> w;for(int j = 0;j <= m;j ++){f[i][j] = min(f[i - 1][j], f[i][max(0, j - v)] + w);//即使物品体积比j大，j - v < 0，也能选，等价于f[i - 1][0]}}cout << f[n][m] << endl;return 0;
}

一维code

#include <iostream>
#include <cstring>using namespace std;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int f[N];int main()
{cin >> n >> m;memset(f, INF, sizeof f);f[0] = 0;for(int i = 1;i <= n;i ++){int v, w;cin >> v >> w;for(int j = m;j >= 0;j --){f[j] = min(f[j], f[max(0, j - v)] + w);//即使物品体积比j大，j - v < 0，也能选，等价于f[0]}}cout << f[m] << endl;return 0;
}

本文发布于:2024-02-05 07:12:18，感谢您对本站的认可！

本文链接：https://www.4u4v.net/it/170727090664307.html

上一篇：背包问题中的“至少至多恰好”问题

下一篇：SQL进阶笔记

标签：背包