洛谷P1060 开心的金明（01背包）

题目描述：点击进入

思路

01背包，套板子

代码

#include<iostream> #include<string> #include<map> //#include<unordered_map> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<iomanip> #include<cmath> #include<fstream> #define X first #define Y second #define best 131 #define INF 0x3f3f3f3f #define P pair<int,int> using namespace std; typedef long long ll; typedef unsigned long long ull; const double eps=1e-5; const double pai=acos(-1.0); const int N=3e4+10; const int maxn=110; const int mod=1e9+7; //const int d[4][2]={0,1,1,0,-1,0,0,-1}; int n,m,v[N],w[N],f[N]; int main() { // ios::sync_with_stdio(false); //memset(f,1e9,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&v[i],&w[i]); } for(int i=1;i<=m;i++) { for(int j=n;j>=v[i];j--)//倒叙是为了保证每个物品都使用一次 { f[j]=max(f[j],f[j-v[i]]+v[i]*w[i]); //在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变 } } printf("%d\n",f[n]); return 0; }

模板（一维）

#include<iostream> #include<string> #include<map> //#include<unordered_map> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<iomanip> #include<cmath> #include<fstream> #define X first #define Y second #define best 131 #define INF 0x3f3f3f3f #define P pair<int,int> using namespace std; typedef long long ll; typedef unsigned long long ull; const double eps=1e-5; const double pai=acos(-1.0); const int N=3e4+10; const int maxn=110; const int mod=1e9+7; //求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。 int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值 int main() { int t,m; memset(f,0,sizeof(f)); //总价值初始化为0 scanf("%d%d",&t,&m); //输入背包承重量t、物品的数目m for(int i=1;i<=m;i++) scanf("%d%d",&w[i],&v[i]); //输入m组物品的重量w[i]和价值v[i] for(int i=1;i<=m;i++) { //尝试放置每一个物品 for(int j=t;j>=w[i];j--) {//倒叙是为了保证每个物品都使用一次 f[j]=max(f[j-w[i]]+v[i],f[j]); //在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变 } } printf("%d\n",f[t]); //输出承重量为t的背包的总价值 return 0; }

模板（二维）

#include<iostream> #include<string> #include<map> //#include<unordered_map> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<iomanip> #include<cmath> #include<fstream> #define X first #define Y second #define best 131 #define INF 0x3f3f3f3f #define P pair<int,int> using namespace std; typedef long long ll; typedef unsigned long long ull; const double eps=1e-5; const double pai=acos(-1.0); const int N=3e4+10; const int maxn=110; const int mod=1e9+7; int w[105],v[105]; int dp[105][1005]; int main() { int t,m,res=-1; scanf("%d%d",&t,&m); for(int i=1;i<=m;i++) scanf("%d%d",&w[i],&v[i]); for(int i=1;i<=m;i++) //物品 { for(int j=t;j>=0;j--) //容量 { if(j>=w[i]) dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } } printf("%d\n",dp[m][t]); return 0; }