看起来似乎没有DFS ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这题原本是一道基本的 01 背包 ， 动态规划 。 只需将价格与重要度提前算好 ， 再套模板即可 。 代码如下 ： 但不会dp的怎么做呢？ 一看数据范围： 其中N<30000N<30000N<30000表示总钱,m<25m<25m<25表示希望购买物品的数量 注意m<25m<25m<25。 225<3.52^{25}<3.5225<3.5 x 10710^7107 也就是说可以dfs！ AC代码

金典的背包

这题原本是一道基本的 01 背包 ， 动态规划 。 只需将价格与重要度提前算好 ， 再套模板即可 。

经典的01背包。主要是读取物品的重量和价值，然后计算在给定背包容量下可以获得的最大价值。 先读取物品的数量 nnn 和背包的容量 mmm。 再读取每个物品的重量 fw[i]fw[i]fw[i] 和价值 v[i]v[i]v[i]，并将价值调整为 v[i]∗=fw[i]v[i] *= fw[i]v[i]∗=fw[i]。 然后用动态规划：用二维数组 f[i][c]f[i][c]f[i][c] 来存储前 iii 个物品在容量为 ccc 时的最大价值。 通过两层循环遍历每个物品和每个可能的容量，然后更新 f[i][c]f[i][c]f[i][c] 的值。 PS:输出在容量为 mmm 时，前 nnn 个物品可以获得的最大价值 f[n][m]f[n][m]f[n][m]。 about the code:

#include<bits/stdc++.h> using namespace std; long long m,n; long long w[33]; long long v[33]; long long dp[30010]; int main(){ cin>>n>>m; for(int i=1;i<=m;i++) cin>>w[i]>>v[i]; for(int i=1;i<=m;i++){ for(int j=n;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+w[i]*v[i]); } cout<<dp[n]; return 0; }

#include<iostream> using namespace std; int w[30],v[30],f[50000],m,n; int main(){ cin>>m>>n; for(int i=1; i<=n; i++){ cin>>v[i]>>w[i]; w[i]*=v[i];} for(int i=1; i<=n; i++) for(int j=m; j>=v[i]; j--) f[j]=max(f[j],f[j-v[i]]+w[i]); cout<<f[m]<<endl; return 0;}

#include<bits/stdc++.h> using namespace std; int dp[100005]; int main(){ int n , m; cin >> n >> m; int w[100005] , j[100005]; for(int i = 1;i <= m;i++) cin >> w[i] >> j[i]; for(int i = 1;i <= n;i++){ for(int k = n;k >= w[i];k--) dp[k] = max(dp[k],dp[k-w[i]] + w[i] * j[i]); } cout << dp[n]; return 0; }