01背包問題
有N件物品和一個容量為V的背包。(每種物品均隻有一件)第i件物品的費用是c[i],價值是w[i]。求解将哪些物品裝入背包可使價值總和最大。
未優化版本:
for (int i=1;i<=n;++i) { for (int j=v;j>=0;--j) {
if(c[i]<=j)//如果目前物品可以放入目前空間的背包
f[i][j]=max(f[i-1][j],f[i-1][j-c[i]]+w[i]);
else f[i][j]=f[i-1][j];//如果目前物品放不進去,那麼繼承前i個物品在目前空間大小時的價值
}
}
優化版本:
/*
01背包
适用于輸入格式如下的問題,出現問題請自行調整:
第一行兩個整數M, N分别表示背包空間與物品總數;
第2到N+1行每行兩個整數,分别表示這類物品每個的價值和所需空間。
*/
#include<cstdio>
const int MAXM=10001,MAXN=51;
int m,n;
int w[MAXN],c[MAXN];
int f[MAXM];
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++)
for(int j=m;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+c[i]);
printf("%d\n",f[m]);
return 0;
}
01背包問題(完全背包)
未優化版本:
for(int i = 0 ; i < n ; i ++)
{
for(int j = 1 ; j <= v ; j++)
{
if(c[i]<=j)
f[i][j] = max(f[i-1][j],f[i][j-c[i]]+w[i]);
else
f[i][j]=f[i-1][j];
}
}
優化版本:
/*
完全背包,輸入規則:
第一行兩個整數M, N分别表示背包空間與物品總數;
第2到N+1行每行兩個整數,分别表示這類物品每個的價值和所需空間。
*/
#include<cstdio>
const int MAXM=10001,MAXN=51;
int m,n;
int w[MAXN],c[MAXN];
int f[MAXM];
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++)
for(int j=w[i];j<=m;j++)
f[j]=max(f[j],f[j-w[i]]+c[i]);
printf("%d\n",f[m]);
return 0;
}
01背包問題(多重背包)
未優化版本:
#include<bits/stdc++.h>
using namespace std;
int dp[1005];
int weight[1005],value[1005],num[1005];
int main()
{
int n,m;
cin>>n>>m;
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
cin>>weight[i]>>value[i]>>num[i];
for(int i=1; i<=n; i++)//每種物品
for(int k=0; k<num[i]; k++)//其實就是把這類物品展開,調用num[i]次01背包代碼
for(int j=m; j>=weight[i]; j--)//正常的01背包代碼
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
cout<<dp[m]<<endl;
return 0;
}
優化版本說明:
把原始的數量的物品拆分可以組合的多個商品,
比如Ci = 14,我們可以把它化成如下4個物品:
重量是Wi,體積是Vi
重量是2 * Wi , 體積是2 * Vi
重量是4 * Wi , 體積是4 * Vi
重量是7 * Wi , 體積是7 * Vi
優化版本:
/*
多重背包,輸入格式:
第一行,一個整數n,物品數量;
第二行,n個整數,第i個整數表示第i個物品的價格bi;
第三行,n個整數,第i個整數表示第i個物品的數量ci;
第四行,一個整數m,背包空間。
*/
#include<cstdio>
const int MAXM=10001,MAXN=6001;
int v[MAXM],w[MAXM];
int f[MAXN];
int n,m,p;
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x,y,s,t=1;
scanf("%d%d%d",&x,&y,&s);
for(;s>=t;t<<=1)
{
v[++p]=x*t;
w[p]=y*t;
s-=t;
}
v[++p]=x*s;
w[p]=y*s;
}
for(int i=1;i<=p;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d\n",f[m]);
return 0;
}
參考文章:
https://www.cnblogs.com/Kalix/p/7622102.html
https://www.cnblogs.com/frankchenfu/p/6445843.html
https://blog.csdn.net/tinyguyyy/article/details/51203935