01背包问题-回溯与动态规划解法

DearXuan

发布于 2022-01-19 18:54:28

6700

发布于 2022-01-19 18:54:28

问题描述

Description 一个旅行者有一个最多能装m公斤的背包，现有n件物品，它们的重量分别是w1,w2,w3,…,wn，它们的价值分别为c1,c2,c3,…,cn。若每种物品只有一件，求旅行者能获得的最大总价值。 Input m，和n（m<=200, n<=30) 接下来共n行每行两个整数wi,ci Output 最大总价值 Sample Input 10 4 2 1 3 3 4 5 7 9 Sample Output 12

回溯方法

数据定义

int m;//背包容量
int n;//物品数目
int weight[30];
int value[30];
int MaxValue = 0;//最大价值
 
int NowWeight = 0;//当前重量
int NowValue = 0;//当前价值

节点

以第i个物品为一个节点，第(i+1)个物品为其儿子节点，左右子树分别表示放入和不放入第i个物品的情况

约束函数

当背包剩余容量不足以放入第i个物品时，其左子树下不可能存在问题的解，因此由剪枝函数终止左子树的遍历

//约束函数，返回第i个物品能否放入背包
bool CheckWeight(int i) {
    if (NowWeight + weight[i] > m) {
        //超重
        return false;
    } else{
        //可以放入
        return true;
    }
}

回溯法

在遍历i的左子树之前，先判断能否放入第i个物品，如果可以，则尝试放入。当遍历左子树完成后，应当取出第i个物品，并遍历右子树

void Search(int i) {
    //i超出范围，说明已经完成了一次DFS
    if(i == n){
        //更新最大价值
        if(NowValue > MaxValue){
            MaxValue = NowValue;
        }
        return;
    }
    //如果可以放入第i个物品，则尝试遍历
    if(CheckWeight(i)){
        //尝试放入第i个物品
        NowWeight += weight[i];
        NowValue += value[i];
        //遍历i的子树
        Search(i + 1);
        //取出第i个物品
        NowWeight -= weight[i];
        NowValue -= value[i];
    }
    //这是在没有放入第i个物品的情况下遍历子树
    Search(i + 1);
}

完整代码

#include <iostream>
 
using namespace std;
 
int m;//背包容量
int n;//物品数目
int weight[30];
int value[30];
int MaxValue = 0;//最大价值
 
int NowWeight = 0;//当前重量
int NowValue = 0;//当前价值
 
void Search(int i);
 
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    Search(0);
    printf("%d",MaxValue);
    return 0;
}
 
//约束函数，返回第i个物品能否放入背包
bool CheckWeight(int i) {
    if (NowWeight + weight[i] > m) {
        //超重
        return false;
    } else{
        //可以放入
        return true;
    }
}
 
void Search(int i) {
    //i超出范围，说明已经完成了一次DFS
    if(i == n){
        //更新最大价值
        if(NowValue > MaxValue){
            MaxValue = NowValue;
        }
        return;
    }
    //如果可以放入第i个物品，则尝试遍历
    if(CheckWeight(i)){
        //尝试放入第i个物品
        NowWeight += weight[i];
        NowValue += value[i];
        //遍历i的子树
        Search(i + 1);
        //取出第i个物品
        NowWeight -= weight[i];
        NowValue -= value[i];
    }
    //这是在没有放入第i个物品的情况下遍历子树
    Search(i + 1);
}

动态规划法

问题分解

判断背包当前状态，需要两个参数，第一个是“剩余容量”，可以决定背包还能放下多少物品；第二个是“物品序号”，它决定背包将会被放入哪些物品

有了这两个参数，就能唯一确定背包的状态，因此一定能求出背包在这种状态下能达到的最大价值

状态函数

定义函数GetMaxValue(int capacity, int i)，参数是上面提到的状态参数，函数返回值是这种状态下背包能达到的最大价值

状态转移

放入或不放入物品i的最大价值与放入或不放入物品(i+1)的最大价值有关

若放入背包，则背包容量减少，背包价值增加，此时的价值为

GetMaxValue(capacity + weight[i],i+1) + value[i]

若不放入背包，则背包容量和价值都不变，直接返回(i+1)时的最大价值

GetMaxValue(capacity,i+1)

取两者的较大值

//返回当前容量为capacity,是否放入物品i时的最大价值
int GetMaxValue(int capacity, int i){
    if(i >= n || capacity >= m) return 0;
    if(capacity + weight[i] > m){
        //放不下物品i，返回是否放入物品(i+1)的最大价值
        return GetMaxValue(capacity,i+1);
    } else{
        //放得下物品i，分别计算放入和不放入物品i的情况，并返回较大值
        return Max(GetMaxValue(capacity + weight[i],i+1) + value[i], GetMaxValue(capacity,i+1));
    }
}

保存结果

为了避免重复计算，将每次计算的结果保存到数组中，下次如果遇到同样的状态，则可以直接返回结果(在本题中效果不明显)

int f[200][30];//记录每次运算的结果
 
//返回当前容量为capacity,是否放入物品i时的最大价值
int GetMaxValue(int capacity, int i){
    if(i >= n || capacity >= m) return 0;
    //如果已经计算过这个状态，则直接返回结果
    if(f[capacity][i] != -1) return f[capacity][i];
    //没有计算过状态，先判断能否放下物品i
    if(capacity + weight[i] > m){
        //放不下物品i，返回是否放入物品(i+1)的最大价值
        f[capacity][i] = GetMaxValue(capacity,i+1);
    } else{
        //放得下物品i，分别计算放入和不放入物品i的情况，并返回较大值
        f[capacity][i] = Max(GetMaxValue(capacity + weight[i],i+1) + value[i], GetMaxValue(capacity,i+1));
    }
    return f[capacity][i];
}

完整代码

#include <iostream>
 
using namespace std;
 
int m;//背包容量
int n;//物品数目
int weight[30];
int value[30];
 
int f[200][30];//记录每次运算的结果
 
int GetMaxValue(int capacity, int i);
 
int main() {
    for(auto & i : f){
        for(int & j : i){
            j = -1;
        }
    }
    scanf("%d%d", &m, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &weight[i], &value[i]);
    }
    printf("%d\n", GetMaxValue(0,0));
    return 0;
}
 
int Max(int a,int b){
    return a>b?a:b;
}
 
//返回当前容量为capacity,是否放入物品i时的最大价值
int GetMaxValue(int capacity, int i){
    if(i >= n || capacity >= m) return 0;
    //如果已经计算过这个状态，则直接返回结果
    if(f[capacity][i] != -1) return f[capacity][i];
    //没有计算过状态，先判断能否放下物品i
    if(capacity + weight[i] > m){
        //放不下物品i，返回是否放入物品(i+1)的最大价值
        f[capacity][i] = GetMaxValue(capacity,i+1);
    } else{
        //放得下物品i，分别计算放入和不放入物品i的情况，并返回较大值
        f[capacity][i] = Max(GetMaxValue(capacity + weight[i],i+1) + value[i], GetMaxValue(capacity,i+1));
    }
    return f[capacity][i];
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021年10月28日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度