美文网首页二叉树之下动态规划
背包问题

背包问题

作者: jdzhangxin | 来源:发表于2018-11-08 20:08 被阅读15次

背包问题

有N种物品和一个容量为W的背包。第i种物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

三种背包

No. 分类 条件
1 0/1背包问题 每种物品只有一个
2 完全背包问题 每种物品有无穷个
3 多重背包 每种物品有有限个n[i]
No. 分类 特点
1 状态 物品i,重量
2 结果 最大价值
3 状态转义 选择物品i,重量和价值增加
4 边界条件 没有可选的物品/所选物品超重

边界条件

No. 分类 说明 处理
1 遍历边界 数组边界 返回0
2 约束边界 超出约束 返回无效值(最值)

模板

  • 01背包问题
for(int i = 1;i <= n;++i){
    for(int j = W;j >= w[i];--j){
        dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
    }
}
  • 完全背包问题
for(int i = 0;i <= n;++i){
    for(int j = w[i];j <= W;++j){
        dp[j] = min(dp[j],dp[j-w[i]]+v[i]);
    }
}
  • 多重背包问题

朴素解法

for(int i = 0;i <= n;++i){
     for(int k = 0;k < b[i];++k){
         for(int j = W;j >= w[i];--j){
             dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
         }
     }
}

举例

01背包问题

有4种物品和一个容量为4的背包。第i种物品的重量是4 3 1 1，价值是30 20 15 20。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入

4 4
30 20 15 20
4 3 1 1

参考代码

#include <bits/stdc++.h>
using namespace std;

int knapsack_01(int n,int W,int* v,int* w){
    int dp[W+1];
    fill_n(dp,W+1,0);
    for(int i=0;i<=n;++i){
        for(int j=W;j>=w[i];--j){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[W];
}
int main() {
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N];
    for(int i=0;i<N;++i){
        scanf("%d",&v[i]);
    }
    int w[N];
    for(int i=0;i<N;++i){
        scanf("%d",&w[i]);
    }
    printf("%d\n",knapsack_01(N-1,W,v,w));
}

完全背包问题

有4种物品和一个容量为4的背包。第i种物品的重量是4 3 1 1，价值是30 20 15 20。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入

4 4
30 20 15 20
4 3 1 1

参考代码

#include <bits/stdc++.h>
using namespace std;

int knapsack_complete(int n,int W,int* v,int* w){
    int dp[W+1];
    fill_n(dp,W+1,0);
    for(int i=0;i<=n;++i){
        for(int j=w[i];j<=W;++j){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[W];
}
int main() {
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N];
    for(int i=0;i<N;++i){
        scanf("%d",&v[i]);
    }
    int w[N];
    for(int i=0;i<N;++i){
        scanf("%d",&w[i]);
    }
    printf("%d\n",knapsack_complete(N-1,W,v,w));
}

多重背包问题

有4种物品和一个容量为4的背包。第i种物品的重量是4 3 1 1，价值是30 20 15 20。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

输入

4 4
30 20 15 20
4 3 1 1
1 2 2 2

参考代码

  • 朴素解法
#include <bits/stdc++.h>
using namespace std;

int knapsack_limitnum(int n,int W,int* v,int* w,int* b){
    int dp[W+1];
    fill_n(dp,W+1,0);
    for(int i=0;i<=n;++i){
        for(int k=0;k<b[i];++k){
            for(int j=W;j>=w[i];--j){
                dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
    }
    return dp[W];
}
int main() {
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N];
    for(int i=0;i<N;++i){
        scanf("%d",&v[i]);
    }
    int w[N];
    for(int i=0;i<N;++i){
        scanf("%d",&w[i]);
    }
    int b[N];
    for(int i=0;i<N;++i){
        scanf("%d",&b[i]);
    }
    printf("%d\n",knapsack_limitnum(N-1,W,v,w,b));
}
  • 二进制优化
#include <bits/stdc++.h>
using namespace std;

int knapsack_01(int n,int W,int* v,int* w){
    int dp[W+1];
    fill_n(dp,W+1,0);
    for(int i=0;i<=n;++i){
        for(int j=W;j>=w[i];--j){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[W];
}

int knapsack_limitnum(int n,int W,int* v,int* w,int* b){
    vector<int> vv;
    vector<int> wv;
    for(int i=0;i<=n;++i){
        int count = b[i];
        for(int j=1;j<=count;j<<1){
           vv.push_back(v[i]*j);
           wv.push_back(w[i]*j);
           count-=j;
        }
        if(count>0){
           vv.push_back(v[i]*count);
           wv.push_back(w[i]*count);
        }
    }
    return knapsack_01(vv.size()-1,W,vv.data(),wv.data());
}
int main() {
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N];
    for(int i=0;i<N;++i){
        scanf("%d",&v[i]);
    }
    int w[N];
    for(int i=0;i<N;++i){
        scanf("%d",&w[i]);
    }
    int b[N];
    for(int i=0;i<N;++i){
        scanf("%d",&b[i]);
    }

    printf("%d\n",knapsack_limitnum(N-1,W,v,w,b));
}
  • 单调队列优化
#include <bits/stdc++.h>
using namespace std;

int knapsack_limitnum(int n,int W,int* v,int* w,int* b) {
    int dp[W+1];
    fill_n(dp,W+1,0);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < w[i]; j++){
            deque<int> p;
            deque<int> q;
            for (int k = j, a = 0; k <= W; k += w[i],a++) {
                if (p.size()==b[i]+1) { 
                    if(q.front()==p.front()) q.pop_front(); 
                    p.pop_front();
                }
                int t = dp[k] - a*v[i];
                p.push_back(t);
                while (!q.empty() && t >= q.back()) q.pop_back();
                q.push_back(t);
                dp[k] = q.front() + a*v[i];
            }
        }
    }
    return dp[W];
}
int main() {
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N];
    for(int i=0;i<N;++i){
        scanf("%d",&v[i]);
    }
    int w[N];
    for(int i=0;i<N;++i){
        scanf("%d",&w[i]);
    }
    int b[N];
    for(int i=0;i<N;++i){
        scanf("%d",&b[i]);
    }
    printf("%d\n",knapsack_limitnum(N-1,W,v,w,b));
}

总结

  1. 先枚举物品，再枚举容量
  2. 01背包问题，逆序枚举容量；完全背包问题，顺序枚举容量。
  3. 状态转移方程是dp[j]=max(dp[j],dp[j-w[i]]+v[i])。
  4. 多重背包是k个01背包问题。

1. 0/1背包问题

1.1 自顶而下(递归)


蓝色节点表示重复计算部分 
#include <bits/stdc++.h>
using namespace std;

int knapsack(int i, int w,int*weights,int*values,vector<int>* dp) {
  if (w == 0) // 刚好装下
    return 0;
  if (weights[i] > w)  // 超重
    return 0;
  if (i < 0)  // 没有物品
    return 0;
  // 选择第i件物品，剩余重量减少，总价值增加，且只能再选择下一件物品
  // 不选择第i件物品，剩余重量不变，总价值不变，且只能再选择下一件物品
  if(0 != dp[i][w]) return dp[i][w];
  return dp[i][w] = max(knapsack(i - 1, w - weights[i],weights,values,dp) + values[i], 
             knapsack(i - 1, w,weights,values,dp));
}

int main(){
    int n,t;
    scanf("%d%d",&n,&t);
    int weights[t];
    int values[t];
    for(int i=0;i<t;++i){
       scanf("%d%d",&weights[i],&values[i]);
    }
    vector<int> dp[t];
    fill_n(dp,t,vector<int>(n+1,0));
    printf("%d\n",knapsack(t-1,n,weights,values,dp));
}

1.2 自底而上(递推)

基本思路：先枚举物品，再枚举容量，如果有足够的容量，则添加进背包。


#include <bits/stdc++.h>
using namespace std;

int knapsack(int t, int n,int*weights,int*values,vector<int>* dp) {
    for(int i=1;i<t;++i){
        for(int w=1;w<=n;++w){
            if(w-weights[i] >= 0){// 放的下
                dp[i][w] = max(dp[i-1][w-weights[i]] + values[i],dp[i-1][w]);
            }else{// 放不下
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[t-1][n];
}
void Print(vector<int>* dp,int t){
    for(int i=0;i<t;++i){
        for(int j=0;j<dp[i].size();++j){
            printf("%d\t",dp[i][j]);
        }
        printf("\n");
    }
}
int main(){
    int n,t;
    scanf("%d%d",&n,&t);
    int weights[t];
    int values[t];
    for(int i=0;i<t;++i){
       scanf("%d%d",&weights[i],&values[i]);
    }
    vector<int> dp[t];
    fill_n(dp,t,vector<int>(n+1,0));
    
    printf("%d\n",knapsack(t,n,weights,values,dp));
    // Print(dp,t);
}

1.3 滚动数组优化

把原来的二维数组压缩成一个一维数组。

#include <bits/stdc++.h>
using namespace std;

int knapsack(int t, int n,int*weights,int*values) {
    int dp[n+1];
    fill_n(dp,n+1,0);
    for(int i=0;i<=t;++i)
        for(int j=n ;j>=weights[i];--j)
            dp[j] = max(dp[j] , dp[j - weights[i]]+values[i]);
    return dp[n];
}
int main(){
    int n,t;
    scanf("%d%d",&n,&t);
    int weights[t];
    int values[t];
    for(int i=0;i<t;++i){
       scanf("%d%d",&weights[i],&values[i]);
    }
    printf("%d\n",knapsack(t-1,n,weights,values));
}

2. 完全背包问题

2.1 自顶而下(递归)

注意，可以重复选择

#include <bits/stdc++.h>
using namespace std;

int knapsack(int i, int w,int*weights,int*values,vector<int>* dp) {
  if (w == 0) // 刚好装下
    return 0;
  if (weights[i] > w)  // 超重
    return 0;
  if (i < 0)  // 没有物品
    return 0;
  // 选择第i件物品，剩余重量减少，总价值增加，且只能再选择下一件物品
  // 不选择第i件物品，剩余重量不变，总价值不变，且只能再选择下一件物品
  if(0 != dp[i][w]) return dp[i][w];
  return dp[i][w] = max(knapsack(i, w - weights[i],weights,values,dp) + values[i], 
             knapsack(i - 1, w,weights,values,dp));
}

int main(){
    int n,t;
    scanf("%d%d",&n,&t);
    int weights[t];
    int values[t];
    for(int i=0;i<t;++i){
       scanf("%d%d",&weights[i],&values[i]);
    }
    vector<int> dp[t];
    fill_n(dp,t,vector<int>(n+1,0));
    printf("%d\n",knapsack(t-1,n,weights,values,dp));
}

2.2 自底而上(递推)

基本思路：先枚举物品，再枚举容量，如果有足够的容量，则添加进背包。注意，可以重复选择

#include <bits/stdc++.h>
using namespace std;

int knapsack(int t, int n,int*weights,int*values,vector<int>* dp) {
    for(int i=1;i<t;++i){
        for(int w=1;w<=n;++w){
            if(w-weights[i] >= 0){// 放的下
                dp[i][w] = max(dp[i][w-weights[i]] + values[i],dp[i-1][w]);
            }else{// 放不下
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[t-1][n];
}
void Print(vector<int>* dp,int t){
    for(int i=0;i<t;++i){
        for(int j=0;j<dp[i].size();++j){
            printf("%d\t",dp[i][j]);
        }
        printf("\n");
    }
}
int main(){
    int n,t;
    scanf("%d%d",&n,&t);
    int weights[t];
    int values[t];
    for(int i=0;i<t;++i){
       scanf("%d%d",&weights[i],&values[i]);
    }
    vector<int> dp[t];
    fill_n(dp,t,vector<int>(n+1,0));
    
    printf("%d\n",knapsack(t,n,weights,values,dp));
    // Print(dp,t);
}

2.3 滚动数组优化

#include <bits/stdc++.h>
using namespace std;

int knapsack(int t, int n,int*weights,int*values) {
    int dp[n+1];
    fill_n(dp,n+1,0);
    for(int i=0;i<=t;++i)
        for(int j=weights[i] ;j<=n;++j)
            dp[j] = max(dp[j] , dp[j - weights[i]]+values[i]);
    return dp[n];
}
int main(){
    int n,t;
    scanf("%d%d",&n,&t);
    int weights[t];
    int values[t];
    for(int i=0;i<t;++i){
       scanf("%d%d",&weights[i],&values[i]);
    }
    printf("%d\n",knapsack(t-1,n,weights,values));
}

3. 多重背包问题

#include <bits/stdc++.h>
using namespace std;

int knapsack_01(int n,int W,int* v,int* w){
    int dp[W+1];
    fill_n(dp,W+1,0);
    for(int i=0;i<=n;++i){
        for(int j=W;j>=w[i];--j){
            dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
    return dp[W];
}

int knapsack_limitnum(int n,int W,int* v,int* w,int* b){
    vector<int> vv;
    vector<int> wv;
    for(int i=0;i<=n;++i){
        int count = b[i];
        for(int j=1;j<=count;j<<1){
           vv.push_back(v[i]*j);
           wv.push_back(w[i]*j);
           count-=j;
        }
        if(count>0){
           vv.push_back(v[i]*count);
           wv.push_back(w[i]*count);
        }
    }
    return knapsack_01(vv.size()-1,W,vv.data(),wv.data());
}
int main() {
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N];
    int w[N];
    int b[N];
    for(int i=0;i<N;++i){
        scanf("%d%d%d",&w[i],&v[i],&b[i]);
    }
    printf("%d\n",knapsack_limitnum(N-1,W,v,w,b));
}
  • 单调队列优化
#include <bits/stdc++.h>
using namespace std;

int knapsack_limitnum(int n,int W,int* v,int* w,int* b) {
    int dp[W+1];
    fill_n(dp,W+1,0);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < w[i]; j++){
            deque<int> p;
            deque<int> q;
            for (int k = j, a = 0; k <= W; k += w[i],a++) {
                if (p.size()==b[i]+1) { 
                    if(q.front()==p.front()) q.pop_front(); 
                    p.pop_front();
                }
                int t = dp[k] - a*v[i];
                p.push_back(t);
                while (!q.empty() && t >= q.back()) q.pop_back();
                q.push_back(t);
                dp[k] = q.front() + a*v[i];
            }
        }
    }
    return dp[W];
}
int main() {
    int N,W;
    scanf("%d%d",&N,&W);
    int v[N];
    int w[N];
    int b[N];
    for(int i=0;i<N;++i){
        scanf("%d%d%d",&w[i],&v[i],&b[i]);
    }
    printf("%d\n",knapsack_limitnum(N-1,W,v,w,b));
}

动态演示

VisualGo测试数据

i=3,w=4
[30,20,15,20]
[4,3,1,1]


蓝色节点表示重复计算部分 
/* base caseS */
if (w == 0 || i < 0) return 0;
if (a2[i] > w) return f(i-1, w);
/* recursive caseS */
return Math.max(
  a1[i] + f(i-1, w-a2[i]), /* take */
          f(i-1, w)); /* not take */

蓝色节点表示重复计算部分 
/* base caseS */
if (w == 0 || i < 0) return 0;
if (a2[i] > w) return 0;
/* recursive caseS */
return Math.max(
  a1[i] + f(i-1, w-a2[i]), /* take */
          f(i-1, w)); /* not take */

混合背包

有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）

for(int i=1;i<=n;i++)
{
    if(第i件物品是01背包)
        for(int j=V;j>=c[i];j--)
            f[j] = max(f[j],f[j-c[i]]+w[i]);
    else if(第i件物品是完全背包)
        for(int j=c[i];j<=V;j++)
            f[j] = max(f[j],f[j-c[i]]+w[i]);
    else if(第i件物品是多重背包)
        MutiplyPack();
}

相关文章

  • 背包问题（完全背包）

    动态规划合集： 1.矩阵链乘法2.投资组合问题3.完全背包问题4.01背包问题5.最长公共子序列 例题3——背包问...

  • Algorithm进阶计划 -- 动态规划（下）

    经典动态规划背包问题最长子序列问题 1. 背包问题 1.1 0-1 背包问题 0-1 背包问题，描述如下： 上面...

  • 背包问题

    0-1背包问题 问题 n个物体，它们各自有重量和价值，给定一个有容量的背包，如何让背包里装入的物体价值总和最大？ ...

  • 背包问题

    问题描述 假如有一个能装下4磅的背包，如何从下列商品列表中选择商品填充背包，使价值达到最大： 动态规划 要解决背包...

  • 背包问题

    （1）0-1背包容量为10的背包，有5种物品，每种物品只有一个，其重量分别为5，4，3，2，1，其价值分别为1，2...

  • 背包问题

  • 背包问题

    01背包（物品只有一个） 有N件物品和一个容量为V的背包。第i建物品的费用是w[i],价值是v[i]。求解将哪些物...

  • 背包问题

    1. 01背包 状态说明：背包体积为v，物品个数为n，f[n,v]表示前n件物品加入背包的最大价值。c_i,w_i...

  • 背包问题

    01背包 优化空间复杂度，变为一维； 外循环依然是n从1->N, 注意内循环 v是从V->0，为什么内循环是V->...

  • 背包问题

    介绍 学习动态规划算法的经典例题。动态规划算法一般有3个特征1、最优化原理：最优解所包含的子问题的解也是最优的。2...

网友评论

    本文标题：背包问题

    本文链接：https://www.haomeiwen.com/subject/azhhoftx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    二叉树之下

    动态规划

    关于我们|服务条款|联系我们|背包问题|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！