01背包
2. 01背包問題 - AcWing題庫
記憶化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int res;
int mem[N][N];
int dfs(int x,int spv)
{
if(mem[x][spv]) return mem[x][spv];
if(x>n) return mem[x][spv]=0;
if(spv>=v[x])
{
return mem[x][spv]=max(dfs(x+1,spv),dfs(x+1,spv-v[x])+w[x]);
}else return mem[x][spv]=dfs(x+1,spv);
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
res=dfs(1,m);
cout<<res;
return 0;
} ?這里補(bǔ)個(gè)圖，DFS是自頂向下推的
dp的遞推是從下往上
?倒序遞推
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int res;
int mem[N][N];
int f[N][N];
int dfs(int x,int spv)
{
if(mem[x][spv]) return mem[x][spv];
if(x>n) return mem[x][spv]=0;
if(spv>=v[x])
{
return mem[x][spv]=max(dfs(x+1,spv),dfs(x+1,spv-v[x])+w[x]);
}else return mem[x][spv]=dfs(x+1,spv);
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
// res=dfs(1,m);
// cout<<res;
// 倒序遞推f[i][j]
// 從第i個(gè)物品開始，選總體積<=j的物品的總價(jià)值的最大值
for(int i=n;i>=1;i--)
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) f[i][j]=f[i+1][j];
else f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
}
}
cout<<f[1][m];
return 0;
} 正序遞推
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int res;
int mem[N][N];
int f[N][N];
int dfs(int x,int spv)
{
if(mem[x][spv]) return mem[x][spv];
if(x<1) return mem[x][spv]=0;
if(spv>=v[x])
{
return mem[x][spv]=max(dfs(x-1,spv),dfs(x-1,spv-v[x])+w[x]);
}else return mem[x][spv]=dfs(x-1,spv);
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
// res=dfs(n,m);
// cout<<res;
// 正序遞推f[i][j]
// 從前i個(gè)物品中選，選總體積<=j的物品的總價(jià)值的最大值
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
} 空間優(yōu)化遞推
用一維數(shù)組代替二維數(shù)組?
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int res;
int f[N],g[N];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) g[j]=f[j];
else g[j]=max(f[j],f[j-v[i]]+w[i]);
}
memcpy(f,g,sizeof(f));
}
cout<<f[m];
return 0;
} 進(jìn)一步優(yōu)化
這里m從m走到0，的原因是只讓每個(gè)物品最多拿一次。
如果正序枚舉體積，就會讓物品被拿多次，從而違反規(guī)則，
但完全背包不用考慮這個(gè)問題，因?yàn)樗旧砭湍苣枚啻蝵
所以完全背包優(yōu)化到一維可以正序枚舉。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int res;
int f[N];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
//if(j<v[i]) f[j]=f[j];//可以省略
if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
} 二維費(fèi)用背包問題(本質(zhì)是01背包）
8. 二維費(fèi)用的背包問題 - AcWing題庫
記憶化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,cap,we;
int v[N],m[N],w[N];
int mem[N][110][110];
int dfs(int x,int spv,int spm)
{
if(mem[x][spv][spm]) return mem[x][spv][spm];
if(x>n) return 0;
if(spv>=v[x]&&spm>=m[x]) return mem[x][spv][spm]=max(dfs(x+1,spv,spm),dfs(x+1,spv-v[x],spm-m[x])+w[x]);
else return mem[x][spv][spm]=dfs(x+1,spv,spm);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>cap>>we;
for(int i=1;i<=n;i++) cin>>v[i]>>m[i]>>w[i];
int res=dfs(1,cap,we);
cout<<res;
return 0;
}倒序遞推
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,cap,we;
int v[N],m[N],w[N];
int mem[N][110][110];
int f[N][110][110];
int dfs(int x,int spv,int spm)
{
if(mem[x][spv][spm]) return mem[x][spv][spm];
if(x>n) return 0;
if(spv>=v[x]&&spm>=m[x]) return mem[x][spv][spm]=max(dfs(x+1,spv,spm),dfs(x+1,spv-v[x],spm-m[x])+w[x]);
else return mem[x][spv][spm]=dfs(x+1,spv,spm);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>cap>>we;
for(int i=1;i<=n;i++) cin>>v[i]>>m[i]>>w[i];
// int res=dfs(1,cap,we);
// cout<<res;
for(int i=n;i>=1;i--)
{
for(int j=0;j<=cap;j++)
{
for(int k=0;k<=we;k++)
{
if(j<v[i]||k<m[i])
{
f[i][j][k]=f[i+1][j][k];
}
else f[i][j][k]=max(f[i+1][j][k],f[i+1][j-v[i]][k-m[i]]+w[i]);
}
}
}
cout<<f[1][cap][we];
return 0;
}正序+二維優(yōu)化
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,cap,we;
int v[N],m[N],w[N];
int mem[N][110][110];
int f[110][110];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>cap>>we;
for(int i=1;i<=n;i++) cin>>v[i]>>m[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=cap;j>=v[i];j--)
{
for(int k=we;k>=m[i];k--)
{
f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
}
}
}
cout<<f[cap][we];
return 0;
}完全背包
3. 完全背包問題 - AcWing題庫
記憶化搜索
完全背包? ?和? ? ? 01背包唯一不同就在于如果當(dāng)前這個(gè)物品可以裝入，在下一次選擇中x不用+1（因?yàn)槲锲肥菬o限多的，還可以再次選擇）
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int mem[N][N];
int dfs(int x,int spv)
{
if(mem[x][spv]) return mem[x][spv];
if(x>n) return 0;
if(spv<v[x]) return mem[x][spv]=dfs(x+1,spv);
else return mem[x][spv]=max(dfs(x+1,spv),dfs(x,spv-v[x])+w[x]);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
int res=dfs(1,m);
cout<<res;
return 0;
}正序遞推?
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j<v[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}優(yōu)化成一維數(shù)組?
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m;
int v[N],w[N];
int f[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
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<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]) ;
}
}
cout<<f[m];
return 0;
}01? ?背包優(yōu)化到一維? ? ? ：逆序枚舉體積
完全背包優(yōu)化到一維? ? ? ：正序枚舉體積
習(xí)題
云剪貼板 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
NASA的食物計(jì)劃（二維費(fèi)用背包問題）
P1507 NASA的食物計(jì)劃 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
記憶化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=60;
int hh,tt,n;
int h[N],t[N],k[N];
int mem[55][410][510];
int dfs(int x,int sph,int spt)
{
if(x>n) return 0;
if(mem[x][sph][spt]) return mem[x][sph][spt];
if(sph>=h[x]&&spt>=t[x])
{
return mem[x][sph][spt]=
max(dfs(x+1,sph,spt),dfs(x+1,sph-h[x],spt-t[x])+k[x]);
}else return mem[x][sph][spt]=dfs[x+1][sph][spt];
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>hh>>tt>>n;
for(int i=1;i<=n;i++) cin>>h[i]>>t[i]>>k[i];
int res=dfs(1,hh,tt);
cout<<res;
return 0;
} 優(yōu)化后的二維數(shù)組遞推
#include<bits/stdc++.h>
using namespace std;
const int N=60;
int hh,tt,n;
int h[N],t[N],k[N];
int f[410][510];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>hh>>tt>>n;
for(int i=1;i<=n;i++) cin>>h[i]>>t[i]>>k[i];
for(int i=1;i<=n;i++)
{
for(int j=hh;j>=h[i];j--)
{
for(int l=tt;l>=t[i];l--)
{
f[j][l]=max(f[j][l],f[j-h[i]][l-t[i]]+k[i]);
}
}
}
cout<<f[hh][tt];
return 0;
} 01背包求體積恰好為M的方案數(shù)
278. 數(shù)字組合 - AcWing題庫
記憶化搜索
?Time Limit Exceeded???
要優(yōu)化成遞推
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int a[N];
int mem[N][10010];
int dfs(int x,int spm)
{
if(spm==0) return 1;
if(x>n) return 0;
if(mem[x][spm]) return mem[x][spm];
if(spm>=a[x]) return mem[x][spm]=dfs(x+1,spm-a[x])+dfs(x+1,spm);
else return mem[x][spm]=dfs(x+1,spm);
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
int res=dfs(1,m);
cout<<res;
return 0;
} 一維數(shù)組遞推
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int a[N];
int f[10010];//記錄方案數(shù)
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
f[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=a[i];j--)
{
f[j]=f[j-a[i]]+f[j];
}
}
cout<<f[m];
return 0;
} 完全背包求體積恰好為M的方案數(shù)
OpenJudge - 6049:買書
記憶化搜索
這個(gè)就能ac了
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int mon[5]={0,10,20,50,100};
int mem[N][N];
int dfs(int x,int spn)
{
if(spn==0) return 1;
if(x>4) return 0;
if(mem[x][spn]) return mem[x][spn];
if(spn>=mon[x]) return mem[x][spn]=dfs(x+1,spn)+dfs(x,spn-mon[x]);
else return mem[x][spn]=dfs(x+1,spn);
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
if(n==0)
{
cout<<"0";
return 0;
}
int res=dfs(1,n);
cout<<res;
return 0;
} 優(yōu)化一下
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int mon[5]={0,10,20,50,100};
int f[N];
signed main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
if(n==0)
{
cout<<"0";
return 0;
}
f[0]=1;
for(int i=1;i<=4;i++)
{
for(int j=mon[i];j<=n;j++)
{
f[j]=f[j]+f[j-mon[i]];
}
}
cout<<f[n];
return 0;
} 背包問題求具體方案
12. 背包問題求具體方案 - AcWing題庫
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int f[N][N];
int v[N],w[N];
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=n;i;i--)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i+1][j];//不選
if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]);
}
}
int i=1,j=m;
while(i<=n)
{
if(j>=v[i]&&f[i+1][j-v[i]]+w[i]>=f[i+1][j])
//如果可以選并且選了之后方案數(shù)會變多
{
cout<<i<<" ";//那就選擇
j-=v[i];//體積減少
i++;
}
else i++;
}
return 0;
}采藥
P1048 [NOIP2005 普及組] 采藥 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
記憶化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int tt,m;
int t[N],v[N];
int mem[110][1010];
int dfs(int x,int spt)
{
if(x>m) return 0;
if(mem[x][spt]) return mem[x][spt];
if(t[x]<=spt)
{
return mem[x][spt]=max(dfs(x+1,spt),dfs(x+1,spt-t[x])+v[x]);
}else return mem[x][spt]=dfs(x+1,spt);
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>tt>>m;
for(int i=1;i<=m;i++) cin>>t[i]>>v[i];
int res=dfs(1,tt);
cout<<res;
return 0;
} 優(yōu)化后
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int tt,m;
int t[N],v[N];
int f[1010];
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>tt>>m;
for(int i=1;i<=m;i++) cin>>t[i]>>v[i];
for(int i=1;i<=m;i++)
{
for(int j=tt;j>=t[i];j--)
{
f[j]=max(f[j],f[j-t[i]]+v[i]);
}
}
cout<<f[tt];
return 0;
} 瘋狂的采藥
P1616 瘋狂的采藥 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
沒別的，這題要注意數(shù)據(jù)范圍?
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=1e7+10;
#define int long long
int tt,m;
int t[N],v[N];
int f[M];
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>tt>>m;
for(int i=1;i<=m;i++) cin>>t[i]>>v[i];
for(int i=1;i<=m;i++)
{
for(int j=t[i];j<=tt;j++)
{
f[j]=max(f[j-t[i]]+v[i],f[j]);
}
}
cout<<f[tt];
return 0;
} 5倍經(jīng)驗(yàn)日
P1802 5 倍經(jīng)驗(yàn)日 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
仔細(xì)讀題?文章來源：http://www.zghlxwxcb.cn/news/detail-435358.html
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define int long long
int n,x;
int l[N],w[N],u[N];
int mem[N][N];
int f[N];
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>x;
for(int i=1;i<=n;i++) cin>>l[i]>>w[i]>>u[i];
for(int i=1;i<=n;i++)
{
for(int j=x;j>=0;j--)
{
if(j>=u[i]) f[j]=max(f[j]+l[i],f[j-u[i]]+w[i]);//服藥能打過就選擇吃藥或者不吃
else f[j]=f[j]+l[i];
}
}
cout<<5*f[x];
return 0;
} 寵物小精靈之收服
OpenJudge - 4978:寵物小精靈之收服文章來源地址http://www.zghlxwxcb.cn/news/detail-435358.html
#include <bits/stdc++.h>
using namespace std;
int dp[1005][505];//dp[i][j][k]:
//(第一維i被優(yōu)化掉）前i個(gè)野生小精靈中最多使用j個(gè)精靈球，
//k點(diǎn)皮卡丘的體力值，能捕捉到的最大小精靈數(shù)量。
int b[105], d[105];//b[i]:收第i小精靈需要的精靈球球數(shù)
//d[i]:收第i小精靈皮卡丘損失的體力值
int main()
{
int n, m, ka, r;
cin >> n >> m >> ka;//n個(gè)精靈球 皮卡丘m點(diǎn)體力值 野生小精靈有ka個(gè)
m--;//不能把m點(diǎn)體力值都用完，最多可以使用m-1點(diǎn)體力
for(int i = 1; i <= ka; ++i)
cin >> b[i] >> d[i];
for(int i = 1; i <= ka; ++i)
for(int j = n; j >= b[i]; --j)
for(int k = m; k >= d[i]; --k)
dp[j][k] = max(dp[j][k], dp[j-b[i]][k-d[i]]+1);//記錄精靈球個(gè)數(shù)
for(int k = 0; k <= m; ++k)//用掉的體力值可以為0，從0開始遍歷
{
if(dp[n][k] == dp[n][m])//d[n][m]收服的數(shù)量肯定是最多的
{//一旦前面有一個(gè)跟dp[n][m]收服的數(shù)量相同，就更新答案
r = m + 1 - k ;//原總體力值為m+1，減去用掉的體力j
break;
}
}
cout << dp[n][m] << ' ' << r;
return 0;
}
到了這里，關(guān)于【DP】學(xué)習(xí)之背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
