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

看起来似乎没有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代码

金典的背包

看似一道绿题，可实际上就一道橙题，小小背包。 本题和A85.采药没啥区别，大家可以对比一下，上代码——

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