背包问题

背包问题

一般背包问题都是不超过容量求最大价值；

另一种是判断能否恰好装满，如果能，求出最大价值；不能输出“impossible”

以零一背包为例： 

最大值：

//二维
#include<bits/stdc++.h>
using namespace std;
const int N=256;
const int inf=0x3f3f3f;
int dp[N][N];
int dp1[N][N];
int V;
int c[N],w[N]; 
int main(){int n;cin>>n>>V;for(int i=1;i<=n;i++){cin>>c[i]>>w[i]; }for(int i=1;i<=V;i++){dp[0][i]=-inf;}for(int i=1;i<=n;i++){for(int j=0;j<=V;j++){dp[i][j]=dp[i-1][j];if(j>=c[i]){dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);}}}for(int i=1;i<=n;i++){for(int j=0;j<=V;j++){dp1[i][j]=dp1[i-1][j];if(j>=c[i]){dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-c[i]]+w[i]);}}}for(int i=0;i<=n;i++){for(int j=0;j<=V;j++){printf("%dt",dp[i][j]);}cout<<endl;}cout<<endl;for(int i=0;i<=n;i++){for(int j=0;j<=V;j++){printf("%dt",dp1[i][j]);}cout<<endl;}return 0;
}

最小值： 

#include<bits/stdc++.h>
using namespace std;
const int N=256;
const int inf=0x3f3f3f;
int dp[N];
int V;
int c[N],w[N]; 
int main(){int n;cin>>n>>V;for(int i=1;i<=n;i++){cin>>c[i]>>w[i]; }
//这里是Vfor(int j=1;j<=V;j++){dp[j]=inf;}for(int i=1;i<=n;i++){for(int j=V;j>=1;j--){if(j>=c[i])dp[j]=min(dp[j],dp[j-c[i]]+w[i]);}}if(dp[V]==inf){cout<<"no"<<endl;	}else{cout<<dp[V];}return 0;
}

 

完全背包的最小值： 

#include<bits/stdc++.h>
using namespace std;
const int N=256;
const int inf=0x3f3f3f;
int dp[N][N];
int dp1[N][N];
int dp2[N];
int V;
int c[N],w[N]; 
int main(){int n;cin>>n>>V;for(int i=1;i<=n;i++){cin>>w[i]>>c[i]; }for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){for(int k=0;k*c[i]<=j;k++){dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j>=c[i])dp1[i][j]=max(dp1[i-1][j],dp1[i][j-c[i]]+w[i]);}}for(int i=1;i<=V;i++){dp2[i]=inf;}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j>=c[i])dp2[j]=min(dp2[j],dp2[j-c[i]]+w[i]);}}if(dp2[V]==inf){cout<<"no"<<endl;	}else{cout<<dp2[V];}return 0;
}