今天是2017/7/11,DCDCBigBig的第二十六篇博文
背包问题应该算是最最基础的DP入门了吧。。。这几天在搞奇怪的DP，无聊来发发背包^_^
背包问题
01背包（一维优化）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,v,f[
10001],c[
10001],w[
10001];
int main(){
memset(f,
0,
sizeof(
0));
scanf(
"%d%d",&n,&v);
for(
int i=
1;i<=n;i++)
scanf(
"%d%d",&c[i],&w[i]);
for(
int i=
1;i<=n;i++){
for(
int j=v;j>=c[i];j--){
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
}
printf(
"%d",f[v]);
return 0;
}
完全背包
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,v,f[
10001],c[
10001],w[
10001];
int main(){
memset(f,
0,
sizeof(
0));
scanf(
"%d%d",&n,&v);
for(
int i=
1;i<=n;i++)
scanf(
"%d%d",&c[i],&w[i]);
for(
int i=
1;i<=n;i++){
for(
int j=c[i];j<=v;j++){
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
}
printf(
"%d",f[v]);
return 0;
}
多重背包
无优化暴力版
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,v,f[
1001][
1001],c[
1001],w[
1001],m[
1001];
int main(){
memset(f,
0,
sizeof(f));
scanf(
"%d%d",&n,&v);
for(
int i=
1;i<=n;i++)
scanf(
"%d%d%d",&c[i],&w[i],&m[i]);
for(
int i=
1;i<=n;i++){
for(
int j=
0;j<=v;j++){
for(
int k=
0;k<=m[i]&&k*c[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-
1][j-k*c[i]]+k*w[i]);
}
}
}
printf(
"%d",f[n][v]);
return 0;
}
二进制优化版
又
