背包问题

背包问题

有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();
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,558评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,002评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,036评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,024评论 1赞 285
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,144评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,255评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,295评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,068评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,478评论 1赞 305
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,789评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,965评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,649评论 4赞 336
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,267评论 3赞 318
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,982评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,223评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,800评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,847评论 2赞 351

推荐阅读更多精彩内容