2021年hznu寒假集训第十一天 背包入门

背包入门"/>

2021年hznu寒假集训第十一天 背包入门

2021年hznu寒假集训第十一天

01背包

给定N个物品和容量是V的背包，以及N个物体的Vi和Wi，每个物体只有一件。 挑选一些物体，使得总体积小于等于V，目标是使得总价值最大，问最大价值是多少？

#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int v[maxn];//物品体积
int w[maxn];//物品价值
int f[maxn][maxn];
int main() {cin >> n >> V;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for (int i = 1; i <= n; i++) {for (int j = v[i]; j <=V ; j++) {f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);}}cout << f[n][V];return 0;
}

空间优化

#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int v[maxn];
int w[maxn];
int f[maxn];
int main() {cin >> n >> V;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}for (int i = 1; i <= n; i++)for (int j = V; j >= v[i]; j--) f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[V];return 0;
}

完全背包

给定N个物品和容量是V的背包，以及N个物体的vi和wi。每个物体有无限多件。 挑选一些物体，使得总体积小于等于V，目标是使得总价值最大，问最大价值是多少？

时间优化

#define judge
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
int n, V;
const int maxn = 1e3 + 10;
int w[maxn], v[maxn];
int f[maxn][maxn];
int main() {cin >> n >> V;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}//------------------------------------------------------------------------------------/*时间优化->优化枚举k,因为1. f[i][j]      =max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,...,f[i-1][j-k*v]+k*w);2. f[i][j-v]   =max(            f[i-1][j-v],     f[i-1][j-2*v]+*w,...,f[i-1][j-k*v]+(k-1)*w);综合1和2 f[i][j]=max(f[i-1][j],f[i][j-v]+w); 其中v是v_i，w是w_i*/for (int i = 1; i <= n; i++)for (int j = 0; j <=V; j++){// for(int j=V;j>= v[i];j--){//错误的写法，因为f[i][j-v]在f[i][j]前面//因此必须等f[i][j-v]更新之后才能更新f[i][j]f[i][j]=f[i-1][j];if(j>=v[i])  f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);}//滚动数组优化cout << f[n][V];return 0;
}

空间优化

// Author: oceanlvr
#include <bits/stdc++.h>
int n, V;
const int maxn = 1e3 + 10;
int w[maxn], v[maxn];
// int f[maxn][maxn];
int f[maxn];
int main() {cin >> n >> V;for (int i = 1; i <= n; i++) {cin >> v[i] >> w[i];}//朴素的完全背包/*for (int i = 1; i <= n; i++)for (int j = V; j >= 0; j--) {f[i][j] = f[i - 1][j];for (int k = 0; k * v[i] <= j; k++)f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);}*///------------------------------------------------------------------------------------/*时间优化->优化枚举k,因为1. f[i][j]      =max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2*v]+2*w,...,f[i-1][j-k*v]+k*w);2. f[i][j-v]   =max(            f[i-1][j-v],     f[i-1][j-2*v]+*w,...,f[i-1][j-k*v]+(k-1)*w);综合1和2 f[i][j]=max(f[i-1][j],f[i][j-v]+w); 其中v是v_i，w是w_i*//*for (int i = 1; i <= n; i++)for (int j = 0; j <=V; j++){// for(int j=V;j>= v[i];j--){//错误的写法，因为f[i][j-v]在f[i][j]前面//因此必须等f[i][j-v]更新之后才能更新f[i][j]f[i][j]=f[i-1][j];if(j>=v[i])  f[i][j]=max(f[i][j-v[i]]+w[i],f[i][j]);}*///滚动数组优化for (int i = 1; i <= n; i++)for (int j = v[i]; j <=V; j++){f[j]=max(f[j-v[i]]+w[i],f[j]);}// cout << f[n][V];cout << f[V];return 0;
}

多重背包

给定N个物品和容量是V的背包，以及N个物体的vi和wi。每个物体有si件。 挑选一些物体，使得总体积小于等于V，目标是使得总价值最大，问最大价值是多少？

int w[maxn];//物品的重量
int v[maxn];//物品的价值
int a[maxn];//物品的数量 
int neww[maxn];//新物品的重量 
int newv[maxn];//新物品的价值 
int dp[maxn];
int n,m;
int num=0;
int main(){int t;cin>>t;while(t--){cin>>m>>n;num=0;//新物品的件数for(int i=1;i<=n;i++){cin>>w[i]>>v[i]>>a[i];for(int j=1;j<=a[i];j*=2){//转化二进制num++;neww[num]=w[i]*j;newv[num]=v[i]*j;a[i]-=j;}if(a[i]){num++;neww[num]=w[i]*a[i];newv[num]=v[i]*a[i];}} for(int i=1;i<=num;i++){for(int j=m;j>=neww[i];j--){dp[j]=max(dp[j],dp[j-neww[i]]+newv[i]);}}cout<<dp[m]<<endl;}
}