首页 > 代码库 > 【0-1 背包模板】 poj 3624
【0-1 背包模板】 poj 3624
先看个未经优化的二维空间dp：
#include <iostream>#include <cstdio>#include <cmath>#include <memory.h>using namespace std;const int maxn1=3500;const int maxn2=1300;int dp[maxn2][maxn2];//int dp[maxn2];int w[maxn1],v[maxn2];int m,n;int max(int x,int y){ return x>y?x:y;}int main(){ freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) cin >> w[i] >> v[i]; } memset(dp,0,sizeof(dp)); int j; for(int i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); else dp[i][j] = dp[i-1][j]; } } cout << dp[n][m] << endl; return 0;}
改进：
1。二维优化到一维
2。倒写
#include <iostream>#include <cstdio>#include <cmath>#include <memory.h>using namespace std;const int maxn1=3500;const int maxn2=13000;int dp[maxn2],w[maxn1],v[maxn2];int m,n;int max(int a, int b){ if(a>b) return a ; else return b ;}int main(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) cin >> w[i] >> v[i]; int j; for(int i=1;i<=n;i++) { for(j=m;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); cout << j << " j "<< dp[j]<< endl; } cout <<endl; } cout << dp[m] << endl; } return 0;}
给一组数据便于理解：
6 j 4
5 j 4
4 j 4
3 j 4
2 j 4
1 j 4
6 j 10
5 j 10
4 j 10
3 j 10
2 j 6
6 j 22
5 j 18
4 j 16
3 j 12
6 j 23
5 j 19
4 j 16
3 j 12
2 j 7
23
最后给出模板：
#include <iostream>#include <cstdio>#include <cmath>#include <memory.h>using namespace std;const int maxn1=3500;const int maxn2=13000;int dp[maxn2],w[maxn1],v[maxn1];int m,n;int max(int a, int b){ if(a>b) return a ; else return b ;}int main(){ //freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) cin >> w[i] >> v[i]; int j; for(int i=1;i<=n;i++) for(j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); cout << dp[m] << endl; } return 0;}
【0-1 背包模板】 poj 3624
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。