01背包题解

题目大意

从个物品中挑出个物品达到最大价值。

分析

每件物品只有两种可能，一种是选，一种是不选，所以分情况讨论即可。

深度优先搜索做法

我们用来求最大值，其中表示在哪一个物品，表示目前剩下的体积，则表示当前这件物品占用的空间，表示这件物品的价值，则我们要求的就是（是背包总容量）。

若，那么没有空间容纳这件物品，只能不选，此时最大价值就为从下一个物品到最后物品所能得到的最大价值，即。

若那么就可以选，选完后为，用表示挑选这一物品后的最大价值。此时的最大价值就是。

最后输出的值就完成了。

广度优先搜索做法

还是只有选与不选两种情况，不过将状态存在队列中。

定义结构体，如下：

struct Node{
    int now, t, sum;
}

其中表示当前要选择的物品，当前剩余体积，目前已获得的最大价值。

用存储当前状态;

初始状态为，将其放入队列。

用来提取每次状态，再将此状态删除，即。就成了我们的研究对象。

类似于深搜，若物品体积大于目前背包容积，即，那么只能不选，则新状态为，再将它放入队列，即。

若物品体积大于当前背包容积，即，那么可以选也可以不选，则有两种新状态：①不选：，②选：。要综合考虑的话就要将两种状态都存下来，所以，。用记录最大值，则当时，，最后输出即可。

记忆化搜索做法

与深搜类似，只是我们需要多开一个数组用来记录深度为体积为时所能获得的最大价值，对于我们已经计算过的值，已经是这个状态所能获得的最大值，不需要重复计算或者更新，所以进行直接调用即可。其本质与动态规划相同。

动态规划做法

动态规划做法(空间复杂度)

若，用记录前件物品给予体积的最大值。则表示上一件物品给定的空间所能获得的最大值。用加上又可得一个值，如果选那么。当然也可以不选，则，所以。

若，此时背包塞不下了，那么前件物品给体积所能获得的最大值就是个物品给定个体积所能获得的最大值，即。

动态规划做法(空间复杂度)

用表示给定的空间所能获得的最大值，则表示给定所能获得的最大值，则的值为与加上后两者的最大值，即。

尤其要注意，循环变量的范围是，并且要从开始循环到。原因：设，，从开始循环，，，被更新，但是，若中已经包括了这件物品，那么也有可能再拿一次(实际上这是完全背包做法)，但这件物品只有一个，用循环到可以避免这一情况。

AC代码

深度优先搜索

#include<bits/stdc++.h>
using namespace std;
int v, n, c[201], w[201];
int dfs(int deep, int t){
    if(deep == n + 1){ //没有物品了，返回0
        return 0;
    }
    if(t < c[deep]){
        return dfs(deep + 1, t); //只能不选
    }
    else{
        return max(dfs(deep + 1, t), dfs(deep + 1, t - c[deep]) + w[deep]); //dfs(deep + 1, t)表示不选, dfs(deep + 1, t - c[deep])表示选
    }
}
int main(){
    scanf("%d%d", &v, &n);
    for(int i = 1;i <= n;i++){
        scanf("%d%d", &c[i], &w[i]);
    }
    printf("%d", dfs(1, v));
    return 0;
}

广度优先搜索

#include<bits/stdc++.h>
using namespace std;
int v, n, c[201], w[201];
struct Node{
	int now, t, sum;
};
queue<Node> q;
int main(){
	scanf("%d%d", &v, &n);
	for(int i = 1;i <= n;i++){
	    scanf("%d%d", &c[i], &w[i]);
	}
	int ans = 0;
	q.push((Node){1, v, 0}); //把初始状态放入队列
    while(!q.empty()){
	    Node e = q.front(); //提取状态
	    q.pop(); //删除状态
	    if(e.now == n + 1){ //没有物品了
		    ans = max(ans, e.sum);
		    continue;
	    }
	    q.push((Node){e.now + 1, e.t, e.sum}); //将不取这件物品获得的新的状态放入队列
    	if(e.t >= c[e.now]){
		    q.push((Node){e.now + 1, e.t - c[e.now], e.sum + w[e.now]}); //将取这件物品获得的新的状态放入队列
	    }
 	}
    printf("%d", ans);
	return 0;
}

记忆化搜索

#include <bits/stdc++.h>
using namespace std;
int v, n, c[201], w[201], dp[201][5001];
int dfs(int deep, int t) {
    if (deep == n + 1) {
        return 0;
    }
    if (dp[deep][t]) {
        return dp[deep][t]; //已经求过，无需重新再求，直接返回dp[deep][t]
    }
    if (t < c[deep]) {
        return dp[deep][t] = dfs(deep + 1, t);
    } else {
        return dp[deep][t] = max(dfs(deep + 1, t), dfs(deep + 1, t - c[deep]) + w[deep]);
    }
}
int main() {
    scanf("%d%d", &v, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &c[i], &w[i]);
    }
    printf("%d", dfs(1, v));
    return 0;
}

动态规划

空间复杂度为的做法

#include<bits/stdc++.h>
using namespace std;
int n, v, c[201], w[201], dp[201][5001];
int main(){
    scanf("%d%d", &v, &n);
    for(int i = 1;i <= n;i++){
        scanf("%d%d", &c[i], &w[i]);
        for(int j = 1;j <= v;j++){
            if(c[i] > j){
                dp[i][j] = dp[i - 1][j];
            }
            else{
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
            }
        }
    }
    printf("%d", dp[n][v]);
    return 0;
}

空间复杂度为的做法（最优做法）

#include<bits/stdc++.h>
using namespace std;
int v, n, c[201], w[201], dp[5001];
int main(){
    scanf("%d%d", &v, &n);
    for(int i = 1;i <= n;i++){
        scanf("%d%d", &c[i], &w[i]);
        for(int j = v;j >= c[i];j--){
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
        }
    }
    printf("%d", dp[v]);
    return 0;
}

共 3 条回复