背包问题——01背包问题与完全背包问题

一、01背包问题(名字由来：每件物品只能用一次)

2. 01背包问题 - AcWing题库https://www.acwing.com/problem/content/description/2/

#include#includeusing namespace std;const int N = 1010;int dp[N][N];  //dp[i][j]表示从前i件物品选出体积不超过j的物品的最大总价值int v[N],w[N];int main(){int n,V;cin>>n>>V;for(int i =1;i>v[i]>>w[i];for(int i =1;i<=n;i++){for(int j =1;j=v[i])dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]]+w[i]);}}cout<<dp[n][V]<<endl;return 0; }

         一维优化：

#include#includeusing namespace std;const int N = 1010;int dp[N];int v[N],w[N];int main() {int n,V;cin>>n>>V;for(int i =1; i>v[i]>>w[i];for(int i =1; i=1; j--) {dp[j] = dp[j];if(j>=v[i])dp[j] = max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[V]<<endl;return 0;}

二、完全背包问题(每件物品使用不限制次数)

3. 完全背包问题 - AcWing题库https://www.acwing.com/problem/content/3/

#include#includeusing namespace std;const int N =1010;int dp[N][N];int w[N],v[N];int n,V;int main(){cin>>n>>V;for(int i =1;i>v[i]>>w[i];for(int i =1;i<=n;i++){for(int j =1;j<=V;j++){ for(int k=0;k*v[i]<=j;k++){ //k为当前物品用几次，k==0时相当于没选这件物品 dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);}}}cout<<dp[n][V];return 0;  } 

         优化1

#include#includeusing namespace std;const int N =1010;int dp[N][N];int w[N],v[N];int n,V;int main(){cin>>n>>V;for(int i =1;i>v[i]>>w[i];for(int i =1;i<=n;i++){for(int j =1;j=v[i])dp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i]);  //通过递推公式可得}}cout<<dp[n][V];return 0;  } 

        优化2

#include#includeusing namespace std;const int N =1010;int dp[N];int w[N],v[N];int n,V;int main(){cin>>n>>V;for(int i =1;i>v[i]>>w[i];for(int i =1;i<=n;i++){for(int j =v[i];j<=V;j++){dp[j] = max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[V]<<endl;return 0;  }