蒟蒻の揹包dp學習總結
0/1揹包
定義
01揹包是在M件物品取出若幹件放在空間爲W的揹包裡，每件物品的體積爲W1，W2至Wn，與之相對應的價值爲P1,P2至Pn。01揹包是揹包問題中最簡單的問題。01揹包的約束條件是給定幾種物品，每種物品有且只有一個，並且有權值和體積兩個屬性。在01揹包問題中，因爲每種物品只有一個，對於每個物品只需要考慮選與不選兩種情況。如果不選擇將其放入揹包中，則不需要處理。如果選擇將其放入揹包中，由於不清楚之前放入的物品佔據了多大的空間，需要列舉將這個物品放入揹包後可能佔據揹包空間的所有情況。
模板
#include<bits/stdc++.h>
using namespace std;
int n,m;//n表示物品數量，m表示總容積
struct node{
int w,v;//w表示體積，v表示價值
}a[10010];
int dp[30010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].v;
}
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i].w;j--){
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
cout<<dp[m];
return 0;
}
例題
P1048 採藥
思路
由題意可得，每株草藥只可採一次，且給定了總揹包容量和每株草藥的資訊，則可判定該題是0/1揹包問題
#include<bits/stdc++.h>
using namespace std;
int t,m;
struct node{
int time,value;
}a[110];
int dp[1010];
int main(){
cin>>t>>m;
for(int i=1;i<=m;i++){
cin>>a[i].time>>a[i].value;
}
for(int i=1;i<=m;i++){
for(int j=t;j>=a[i].time;j--){
dp[j]=max(dp[j],dp[j-a[i].time]+a[i].value);
}
}
cout<<dp[t];
return 0;
}
P1049 裝箱問題
思路
該題僅給定了每件物品的體積和揹包總容量，但是題目中隱晦地告訴我們：價值就是每件物品的體積！ ，故此題只需使用0/1揹包模板求所佔的最大體積，最後輸出總體積-求所佔的最大體積即可，是一道0/1揹包基礎變形題
#include<bits/stdc++.h>
using namespace std;
int n;
int a[40];
int v;
int dp[20010];
int main(){
cin>>v>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
for(int j=v;j>=a[i];j--){
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
}
cout<<v-dp[v];
return 0;
}
P1060 開心的金明
思路
由題意可得，該題的**每件價值爲體積（每件物品所花錢數）* 重要度 **，那麼這題就變成了常規的0/1問題，故此題只需仔細讀題即可求出答案
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int w,v;
}a[30];
int dp[30010];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i].w>>a[i].v;
a[i].v*=a[i].w;
}
for(int i=1;i<=m;i++){
for(int j=n;j>=a[i].w;j--){
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
cout<<dp[n];
return 0;
}
完全揹包
定義
有N種物品和一個容量爲V的揹包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入揹包可使這些物品的費用總和不超過揹包容量，且價值總和最大。
模板
#include<bits/stdc++.h>
using namespace std;
int n,m;//n表示物品數量，m表示總容積
struct node{
int w,v;//w表示體積，v表示價值
}a[10010];
int dp[30010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].v;
}
for(int i=1;i<=n;i++){
for(int j=a[i].w;j<=m;j++){
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
cout<<dp[m];
return 0;
}
例題
P1616 瘋狂的採藥
思路
由題意可得，每株草藥可採無限次，也給定了每株草藥的資訊和總容積，則該題爲一道完全揹包題
#include<bits/stdc++.h>
using namespace std;
int t,m;
struct node{
int v,w;
}a[10010];
int dp[10000010];
int main(){
cin>>t>>m;
for(int i=1;i<=m;i++){
cin>>a[i].w>>a[i].v;
}
for(int i=1;i<=m;i++){
for(int j=a[i].w;j<=t;j++){
dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
}
}
cout<<dp[t];
return 0;
}
P5662 紀念品
思路
**這題題面有一句關鍵的話，「當日購買的紀念品也可以當日賣出換回金幣」！**這句話可以幫我們簡化狀態，因爲如果一個紀念品，你想連續持有若幹天，可以看做第一天買，第二天早上立刻賣掉，然後第二天買回來，第三天早上立刻賣掉，然後第三天買回來……所以我們就不需要記錄每天手裏持有多少紀念品了，統一認爲我們今天買的紀念品，明天早上就立刻賣掉。明天又是新的一天，用所有的現金，進行新的決策就好了。
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int a[110][110];
int dp[10100];
int main(){
cin>>t>>n>>m;
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=t;i++){
memset(dp,0,sizeof(dp));
for(int j=1;j<=n;j++)
for(int k=a[i][j];k<=m;k++)
dp[k]=max(dp[k],dp[k-a[i][j]]+a[i+1][j]-a[i][j]);
m=max(dp[m]+m,m);
}
cout<<m;
return 0;
}
多重揹包
定義
有N種物品和一個容量爲V的揹包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入揹包可使這些物品的費用總和不超過揹包容量，且價值總和最大。
模板
#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[110],w[110],s[110];
int dp[110];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
for(int k=1;k<=s[i]&&k*v[i]<=j;k++){
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[m];
return 0;
}