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

问题描述

Description
一个旅行者有一个最多能装m公斤的背包,现有n件物品,它们的重量分别是 $w_1$ , $w_2$ , $w_3$ ,…, $w_n$ ,它们的价值分别为 $c_1$ , $c_2$ , $c_3$ ,…, $c_n$ .若每种物品只有一件,求旅行者能获得的最大总价值.
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)的最大价值有关

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

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

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

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];
}