长春火车站停车场24小时收费标准,中铁建设门户网员工登录,wordpress加a标签图片,vs做网站时怎么弹出窗口有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件#xff0c;每件体积是 vi#xff0c;价值是 wi。 求解将哪些物品装入背包#xff0c;可使物品体积总和不超过背包容量#xff0c;且价值总和最大。 输出最大价值。
输入 第一行两个整数#xff0c;N#xf…有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件每件体积是 vi价值是 wi。 求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。 接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出 输出一个整数表示最大价值。
Input 4 5 1 2 3 2 4 1 3 4 3 4 5 2
Output 10
根据不同的数据范围有不同的选择 Ⅰ. 数据范围 0N,V≤100 0vi,wi,si≤100
直接写
//代码一
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N510,M6010;
int n,m;
int v,w,s;
int f[N][M];
void solve()
{cinnm;for (int i1;in;i){cinvws;for (int j1;jm;j)for (int k0;ksk*vj;k)f[i][j]max(f[i][j],f[i-1][j-k*v]k*w);}coutf[n][m];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}//代码二:降一维
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N510,M6010;
int n,m;
int v,w,s;
int f[M];
void solve()
{cinnm;for (int i1;in;i){cinvws;for (int jm;jv;j--)for (int k0;ksk*vj;k)f[j]max(f[j],f[j-k*v]k*w);}coutf[m];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
} Ⅱ. 数据范围 0N≤10000V≤20000vi,wi,si≤2000
通过二进制将每种物品按照个数的不同重新打包再按01背包的方式选择
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N1e610;
int n,m;
int f[N],v[N],w[N];
int cnt;
void solve()
{cinnm;for (int i1;in;i){int a,b,s;cinabs;int k1;while (ks){cnt;v[cnt]k*a;w[cnt]k*b;s -k;k *2;}if (s0){cnt;v[cnt]s*a;w[cnt]s*b;}}for (int i1;icnt;i)for (int jm;jv[i];j--)f[j]max(f[j],f[j-v[i]]w[i]);coutf[m];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
} Ⅲ. 数据范围 0N≤10000V≤200000vi,wi,si≤20000
通过单调队列来更新状态
//代码一
#include bits/stdc.h
using namespace std;
//#define int long long //不开就不开吧
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N1010,M2e410;
int n,m;
int f[N][M],q[M];
void solve()
{cinnm;for (int i1;in;i){int v,w,s;cinvws;for (int j0;jv;j){int hh0,tt-1;for (int kj;km;k v){if (hhttk-q[hh]s*v) hh; //判断队头是否滑出窗口队列中的v不能超过上限s个while (hhttf[i-1][q[tt]]-(q[tt]-j)/v*wf[i-1][k]-(k-j)/v*w) tt--;q[tt]k;f[i][k]f[i-1][q[hh]](k-q[hh])/v*w;}}}coutf[n][m];
}
int main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}//代码二 降一维
#include bits/stdc.h
using namespace std;
//#define int long long //不开就不开吧
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N2e410;
int n,m;
int f[N],g[N],q[N];
void solve()
{cinnm;for (int i1;in;i){int v,w,s;cinvws;memcpy(g,f,sizeof f); //滚动数组备份上一次的状态for (int j0;jv;j){int hh0,tt-1;for (int kj;km;k v){if (hhttk-q[hh]s*v) hh; //判断队头是否滑出窗口队列中的v不能超过上限s个while (hhttg[q[tt]]-(q[tt]-j)/v*wg[k]-(k-j)/v*w) tt--;q[tt]k;f[k]g[q[hh]](k-q[hh])/v*w;}}}coutf[m];
}
int main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}
