[动态规划] 浮点数0-1背包问题

2023-12-18 16:40:59

0-1背包问题

题目描述

给定 n 种物品和一背包。物品 i 的重量是 wi,其价值为 pi,背包的容量为 m。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大?

关于输入

输入数据共有 n 行,
第一行有一个整数 n 和一个实数 m,分别为物品数和背包容量。
接下来有 n 行,每行有两个实数,分别为物品 i 的重量和价值

(背包的容量和物品i的重量最多为2位小数,且有效数字不会超过10^6)

关于输出

数出数据只有一个实数,它表示最大的总价值。要求精确到小数点后 5 位

例子输入
3 10
8 10
3 8
3 8
例子输出
16.00000
解题分析

首先,为了方便我们使用动态规划的策略,我们可以选择将读入的背包容量和物品都乘上100,将浮点数先变成整数,这样我们就可以用dp数组去考虑所有的情况了。

然后,本题的dp数组如果是一维的话,是不足以描述清楚问题的,故我们设定的dp数组应为2维,即dp[i][j],接下来,考虑一下i,j代表的含义。

我们不妨这样规定,i为前i个物品,j为背包的容量,由于每个物品只能选一次,故我们需要从后往前递推,用两层循环去更新我们的dp数组,第一层循环是考虑第几个物品,第二层循环是在当前物品考虑数下,所有的背包容量取最大物品价值时,背包可容下的最大价值。

本代码实现了一种著名的动态规划算法,用于解决0-1背包问题。这个问题的主要挑战在于,有一系列的物品和一个背包,每个物品都有自己的重量和价值,需要决定应该放哪些物品到背包中,以便使得背包中的总价值最大,同时不超过背包的容量。

这个问题的关键是,对于每个物品,要么选择放入背包,要么选择不放。这就是问题名称中的"0-1"的由来。不能选择将一个物品的一部分放入背包。

本代码的核心思想是,对于每个物品,考虑所有可能的背包剩余容量,然后决定是否将该物品放入背包。这通过一个二维的动态规划表格来实现。

在代码中,`dp[j]`表示在背包剩余容量为`j`时的最大价值。`w[i]`和`v[i]`分别表示第`i`个物品的重量和价值。

首先,所有物品的重量和背包的容量都乘以100,这是为了将问题转化为整数问题,避免处理浮点数带来的复杂性。

然后,代码使用两个嵌套的循环。外层循环遍历所有的物品,内层循环遍历所有可能的背包剩余容量。

对于每个物品和每个可能的背包剩余容量,考虑两种可能的情况:一种是不放入这个物品,即保持当前的价值不变;另一种是放入这个物品,即将背包的剩余容量减去这个物品的重量,然后加上这个物品的价值。代码使用`max`函数来选择这两种情况中的最大值。

最后,输出在背包容量为`m`时的最大价值,即`dp[int(m)]`。这就是问题的答案。

总的来说,本代码是一个典型的动态规划算法的实现,通过在所有可能的物品和背包剩余容量之间进行穷举,找到了问题的最优解。

#include <iostream>
#include <iomanip>
using namespace std;

double dp[100000];
double w[10000];
double v[10000];

int main() {
	int n; double m; cin>>n>>m;
	m*=100;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
		w[i]*=100;
	}
	for(int i=1;i<=n;i++){
		for(int j=int(m);j>=w[i];j--){
			dp[j]=max(dp[j],dp[int(j-w[i])]+v[i]);
		}
	}
	cout<<fixed<<setprecision(5)<<dp[int(m)]<<endl;
	return 0;
}

?或者

#include<stdio.h>

#define MAXN 1000
#define MAXM 100000

double max(double a, double b) {
    return a > b ? a : b;
}

double w[MAXN], p[MAXN], dp[MAXM];

int main() {
    int n;
    double m;
    scanf("%d%lf", &n, &m);
    m *= 100; // 将背包的容量乘以100
    for(int i = 1; i <= n; i++) {
        scanf("%lf%lf", &w[i], &p[i]);
        w[i] *= 100; // 将物品的重量乘以100
    }
    for(int i = 1; i <= n; i++) {
        for(int j = (int)m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[(int)(j-w[i])] + p[i]);
        }
    }
    printf("%.5lf\n", dp[(int)m]); 
    return 0;
}

当然,本题也可以用记忆化搜索的方法直接去计算,定义f(k,m)为考虑从第k个物品开始一直到最后一个物品,容量还有m的情况下,背包可以装下的最大价值的物品总和。

这段代码也是使用动态规划来解决0-1背包问题,但它使用了递归的方式来实现。递归方法的优点是代码更加简洁和直观,但可能会导致更高的计算复杂性,特别是在没有使用记忆化优化的情况下。

这段代码的主要部分是`getmax`函数。这个函数接受两个参数:当前考虑的物品的索引`k`和背包的剩余容量`content`。函数的返回值是在这种条件下可以获得的最大价值。

函数首先检查两种基本情况:如果所有的物品都已经被考虑过了,或者背包已经没有剩余容量,那么最大价值就是0。

接下来,函数检查动态规划表格`dp`中是否已经计算过这种情况的最大价值。如果已经计算过,那么就直接返回这个值,这就是所谓的记忆化优化,可以避免重复计算。

然后,函数考虑两种可能的情况:一种是不放入当前的物品,即`plan_a`;另一种是放入当前的物品,即`plan_b`。对于后者,需要检查当前的物品是否能够放入背包,即它的重量是否不超过背包的剩余容量。

最后,函数返回这两种情况的最大值,并将这个值存入动态规划表格`dp`中,以便后续的查找。

在`main`函数中,首先读入物品的数量和背包的容量,然后读入每个物品的重量和价值。然后,调用`getmax`函数计算最大的价值,并将结果输出。

总的来说,这段代码是一个动态规划算法的递归实现,通过记忆化优化避免了重复计算,从而提高了效率。

#include <iostream>
#include <iomanip>
using namespace std;
int n; double m;
double w[1000],p[1000];
double dp[1000][10000];

double getmax(int k,double content){
    if(k==n+1){
        return 0;
    }
    if(content<=0){
        return 0;
    }
    if(dp[k][int(content*100)]!=0){
        return dp[k][int(content*100)];
    }
    double plan_a=getmax(k+1,content);
    double plan_b=0;
    if(w[k]<=content){
       plan_b=getmax(k+1,content-w[k])+p[k];
    }
    return dp[k][int(content*100)]=max(plan_a,plan_b);
}

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>p[i];
    }
    cout<<fixed<<setprecision(5)<<getmax(1,m);
	return 0;
}

文章来源:https://blog.csdn.net/StudyingPanda/article/details/135063396
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。