背包问题全解＜y总AcWing＞

背包问题全解＜y总AcWing＞
文章目录
- 背包九讲
  一、01背包问题
  二、完全背包问题
  三、多重背包问题
  四、混合背包问题
  五、二维费用的背包问题
  六、分组背包问题
  七、背包问题求方案数
  八、背包问题求最优的物品方案
  九、有依赖的背包问题
背包九讲

思想解析：闫氏DP分析法，从此再也不怕DP问题！_哔哩哔哩_bilibili

题目以及解析来源：题库 - AcWing

推荐博客：dd大牛的《背包九讲》 - 贺佐安 - 博客园 (cnblogs.com)

一、01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 0i,w_i≤1000

输入样例
```
4 5
1 2
2 4
3 4
4 5
1
2
3
4
5
```
输出样例：
```
8
1
```
解析：
```
/*
f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
f[i][j]:
    1.不选第i个物品：f[i][j]=f[i-1][j]
    2.选第i个物品：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]) （当j>v[i]时）
*/

#include
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]){
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }
    }
    cout<
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
解析优化使用一维空间

01背包问题空间优化的原理是：
我们其实还是进行双重循环
1. 外层for还是用来遍历原来二维数组的每一行（虽然现在已经没有二维数组了，但是表示的还是这个意义，只不过是用一维数组一直通过外层循环将每一行的值更新）
2. 内层循环就是在更新二维数组（同上一个括号内的说法）的每一行中的每一列的值。
3. 因此我们还想用上一行的值得时候，就不能从前往后了，要从后往前，更新某行最后一个值的时候，其实前面的值存储的还是上一行的所有值，所以不受影响。
```
#include
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<
```
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
二、完全背包问题

有 N 件物品和一个容量是 V 的背包。每件物品可以无限用。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 0i,w_i≤1000

输入样例
```
4 5
1 2
2 4
3 4
4 5
1
2
3
4
5
```
输出样例：
```
10
1
```
解析：
```
/*
f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少
f[i][j]:
    1.不选第i个物品：f[i][j]=f[i-1][j]
    2.选第i个物品：
        f[i][j]=max(f[i-1][j], ..... ,f[i-1][j-k*v[i]]+k*w[i], ....) （当j>k*v[i]时）
        f[i][j-v[i]]=max(f[i-1][j-v[i]], ..... ,f[i-1][j-k*v[i]]+(k-1)*w[i], ....) （当j>k*v[i]时）
        两个公式相差值为w[i]
        故f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
*/

#include
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
    }
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i]){
                f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
            }
        }
    }
    cout<
```

优化成一维空间

/*
f[i]表示总体积是i的情况下，总价值最大是多少

数学归纳法：
1.假设考虑前i-1个物品之后。所有的f[j]都是正确的
2.来证明：考虑完第i个物品后，所有的f[j]也都是正确的

队友某个j而言，如果最优解中包含k个v[i]
f[j-k*v[i]]
f[j-(k-1)*v[i]-v[i]]+w[i] 包含1个v[i]
...
f[j] f[j-v[i]]+w[i]
*/

#include
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];
        for(int j=v[i];j<=m;j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<

三、多重背包问题

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

第一行两个整数，N，V用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i,s_i用空格隔开，分别表示第 i 件物品的体积和价值和数量。

/* f[i]总体积是i的情况下，最大价值是多少 1.f[i]=0 f[m] 2.f[0]=0,f[i]=-INF,i!=0 max{f[0 .... m]} */ #include using namespace std; const int N=1010; int n,m; int v[N],w[N],s[N]; int f[N]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]>>s[i]; } for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ for(int k=1;k*v[i]<=j&&k<=s[i];k++){ f[j]=max(f[j],f[j-k*v[i]]+k*w[i]); } } } cout<

/* v,w 多数量物品拆成单一物品放到数组当中去二进制拆法： log(s)上取整 s - 1 - 2 - 4 - 8 直到为负数，将最后的s拿出来 */ #include using namespace std; const int N=2010; int n,m; int v,w,s; int f[N]; struct Good{ int v,w; }; int main(){ vector goods; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v>>w>>s; for(int k=1;k<=s;k*=2){ s-=k; goods.push_back({v*k,w*k}); } if(s>0) goods.push_back({v*s,w*s}); } for(auto good:goods) for(int j=m;j>=good.v;j--) f[j]=max(f[j],f[j-good.v]+good.w); cout<

/* f[j] = f[j-v]+w, f[j-2*v]+2w, ... f[j-k*v]+w f[j+v]=f[j]+w, f[j-v]+2*w */ #include using namespace std; const int N=20010; int n,m; int f[N],g[N],q[N]; int main(){ cin>>n>>m; for(int i=0;i>v>>w>>s; memcpy(g,f,sizeof(f)); for(int j=0;jq[hh]) hh++; if(hh<=tt) f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w); while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w) tt--; q[++tt]=k; } } } cout<

#include using namespace std; int n,m,v[100010],w[100010],f[100010]; int main(){ cin>>n>>m; int cnt=1; for(int i=1;i<=n;i++){ int a,b,s; cin>>a>>b>>s; int k=1; if(s<0)s=1; else if(s==0)s=m/a;//把01背包和多重背包先转化成多重背包，若为完全背包，则在最优情况下，只能取总体积/该物品体积向下取整 while(k<=s){ v[cnt]=a*k; w[cnt]=b*k; s-=k; k*=2; cnt++; } if(s>0){ v[cnt]=s*a; w[cnt]=s*b; cnt++; } }//将多重背包进行二进制优化，变成01背包 for(int i=1;i<=cnt;i++){ for(int j=m;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+w[i]); } }//01背包问题 cout<

#include using namespace std; int n, V, M; const int N=1e3+5; int v[N],m[N],w[N],f[N][N]; signed main(){ cin>>n>>V>>M; for(int i=1;i<=n;i++) { cin>>v[i]>>m[i]>>w[i]; } for (int i = 1; i <= n; i ++) for (int j = V; j >= v[i]; j --) for (int k = M; k >= m[i]; k --) f[j][k] = max(f[j - v[i]][k - m[i]] + w[i], f[j][k]);//动态转移方程，01 背包的思路 cout<

#include using namespace std; const int N=110; int f[N][N]; //只从前i组物品中选，当前体积小于等于j的最大值 int v[N][N],w[N][N],s[N]; //v为体积，w为价值，s代表第i组物品的个数 int n,m,k; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>s[i]; for(int j=0;j>v[i][j]>>w[i][j]; } } for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ f[i][j]=f[i-1][j]; for(int k=0;k=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]); } } } cout<

#include using namespace std; const int N=110; int f[N],v[N],w[N]; int n,m,k; int main(){ cin>>n>>m; for(int i=0;i>s; for(int j=0;j>v[j]>>w[j]; } for(int j=m;j>=0;j--){ for(int k=0;k=v[k]) f[j]=max(f[j],f[j-v[k]]+w[k]); } } } cout<

#include #include using namespace std; const int N = 1010, mod = 1000000007; int n, m; int f[N], g[N]; int v[N], w[N]; int main() { cin >> n >> m; for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i]; for (int i = 0; i <= m; i ++ ) g[i] = 1; for (int i = 1; i <= n; i ++ ) for (int j = m; j >= v[i]; j -- ) { int left = f[j], right = f[j - v[i]] + w[i]; f[j] = max(left, right); if (left > right) g[j] = g[j]; else if (left < right) g[j] = g[j - v[i]]; else g[j] = g[j] + g[j - v[i]]; g[j] %= mod; } cout << g[m] << endl; return 0; }

#include #include #include using namespace std; int dp[1010][1010]; int n, m; int v[1010]; int w[1010]; int main() { cin >> n >> m; int i = 0; for (i = 1; i <= n; i++) { cin >> v[i] >> w[i]; } int l = 1; int r = n; while (l < r) { swap(v[l], v[r]); l++; r--; } l = 1; r = n; while (l < r) { swap(w[l], w[r]); l++; r--; } vector vvv; for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { // 默认不选 dp[i][j] = dp[i - 1][j]; if (j >= v[i]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]); } } } for (int i = n; i >= 1; i--) { if (m >= v[i] && dp[i][m] == dp[i - 1][m - v[i]] + w[i]) { //可以选 cout << n+1-i << " "; m = m - v[i]; } } return 0; }

#include #include using namespace std; int f[110][110];//f[x][v]表达选择以x为子树的物品，在容量不超过v时所获得的最大价值 vector g[110]; int v[110],w[110]; int n,m,root; int dfs(int x) { for(int i=v[x];i<=m;i++) f[x][i]=w[x];//点x必须选，所以初始化f[x][v[x] ~ m]= w[x] for(int i=0;i=v[x];j--)//j的范围为v[x]~m, 小于v[x]无法选择以x为子树的物品 { for(int k=0;k<=j-v[x];k++)//分给子树y的空间不能大于j-v[x],不然都无法选根物品x { f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]); } } } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { int fa; cin>>v[i]>>w[i]>>fa; if(fa==-1) root=i; else g[fa].push_back(i); } dfs(root); cout<

#include #include #include using namespace std; const int N = 110; int n,m; int h[N],e[N],ne[N],idx; /*h数组是邻接表的头它的下表是当前节点的标号，值是当前结点第一条边的编号（其实是最后加入的那一条边），e数组是边的集合，它的下标是当前边的编号，数值是当前边的终点； ne是nextedge，如果ne是-1表示当前结点没有下一条边，ne的下标是当前边的编号，数值是当前结点的下一条边的编号，idx用于保存每一条边的上一条边的编号。这样我们就知道了当前结点的第一条边是几，这个边的终点是那个结点，该节点的下一条边编号是几，那么邻接表就完成了 */ int v[N],w[N],f[N][N]; void add(int a,int b){ e[idx] = b,ne[idx] = h[a],h[a] = idx++;//该方法同于向有向图中加入一条边，这条边的起点是a，终点是b，加入的这条边编号为idx } void dfs(int u){ for(int i = h[u];i!=-1;i = ne[i]){//对当前结点的边进行遍历 int son = e[i];//e数组的值是当前边的终点，即儿子结点 dfs(son); for(int j = m-v[u];j>=0;j--){ //遍历背包的容积，因为我们是要遍历其子节点，所以当前节点我们是默认选择的。 //这个时候当前结点我们看成是分组背包中的一个组，子节点的每一种选择我们都看作是组内一种物品，所以是从大到小遍历。 //我们每一次都默认选择当前结点，因为到最后根节点是必选的。 for(int k = 0;k<=j;k++){//去遍历子节点的组合 f[u][j] = max(f[u][j],f[u][j-k]+f[son][k]); } } } //加上刚刚默认选择的父节点价值 for(int i = m;i>=v[u];i--){ f[u][i] = f[u][i-v[u]]+w[u]; } //因为我们是从叶子结点开始往上做，所以如果背包容积不如当前物品的体积大，那就不能选择当前结点及其子节点，因此赋值为零 for(int i = 0;i>n>>m; int root; for(int i = 1;i<=n;i++){ int p; cin>>v[i]>>w[i]>>p; if(p==-1){ root = i; }else{ add(p,i);//如果不是根节点就加入邻接表,其中p是该节点的父节点，i是当前是第几个节点 } } dfs(root); cout<

背包问题全解 ＜y总AcWing＞

文章目录

背包九讲

一、01背包问题

二、完全背包问题

三、多重背包问题

四、混合背包问题

五、二维费用的背包问题

六、分组背包问题

七、背包问题求方案数

八、背包问题求最优的物品方案

九、有依赖的背包问题