给定 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;
}