01背包和完全背包
GitHub 参考链接 (opens new window)
# 01 背包
# 1、01 背包暴力解法，回溯问题
#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+5;
int w[N],v[N];
int ans,n,V;
void dfs(int now,int sw,int sv){
if(now==n+1){
ans=max(ans,sv);
return;
}
dfs(now+1,sw,sv);
if(sw+w[now]<=V)dfs(now+1,sw+w[now],sv+v[now]);
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> V;
for (int i = 1; i <= n; ++i) {
cin >> w[i] >> v[i];
}
dfs(1, 0, 0);
cout<<ans;
return 0;
}
# 2、动态规划解法
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
using ll = long long;
ll dp[N][N];// dp[i][j] 表示 第 i 件物品，j 容量，的最大价值
int n,V;
int main() {
// dp[i-1][j] //不放物品
// dp[i-1][j-w[i]]+v[i] //放物品
cin>>n>>V;
for(int i=1;i<=n;i++){
ll w,v;cin>>w>>v;
for(int j=0;j<=V;j++){
if(j>=w)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][V];
return 0;
}
# 3、01 背包代码优化
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
using ll = long long;
ll dp[N];
int n,V;
int main() {
// dp[j] = max(dp[j],dp[j-w]+v); //表示此时物品总重量为 j 的情况下的最大价值
cin>>n>>V;
for(int i=1;i<=n;i++){
ll w,v;cin>>w>>v;
for(int j=V;j>=w;j--){
dp[j]=max(dp[j],dp[j-w]+v);
}
}
cout<<dp[V];
return 0;
}
# 4、例题 1：背包与魔法
在背包的基础上加了一个判断，先写背包问题的一般写法，可以过掉 40%，在考虑去优化。 对于每个物品有 3 种选择，可以不选、选但不用魔法、选且用魔法。
示例代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e4+5;
ll dp[N][2];// 设状态 dp[i][j] 表示物品总重量为 i，且使用了 j 次魔法情况下的最大值 ,j = 0 or 1
int n,w,v,M,K;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>M>>K;
for(int i=1;i<=n;i++){
cin>>w>>v;
// 优化为1维数组来写
for(int j=M;j>=0;j--){
if(j>=w){
dp[j][0]=max(dp[j][0],dp[j-w][0]+v);
dp[j][1]=max(dp[j][1],dp[j-w][1]+v);
}
if(j>=w+K){
dp[j][1]=max(dp[j][1],dp[j-w-K][0]+2*v);
}
}
}
cout<<max(dp[M][0],dp[M][1]);
return 0;
}
# 5、例题 2：倒水
就算是不倒水，那么客人的满意度就有 e。
如果水少于 a 那么我们就不倒水，满意度为 3；
如果大于等于 a 且小于 c 那么我们倒 a 毫升，满意度为 b；
大于等于 c 的话倒 c 毫升，满意度为 d。
我们就可以设置状态 dp[i][j]表示前 i 个人需要 j 毫升水的最大满意度。
示例代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m;
ll dp[1005][1005];//dp[i][j] 表示前i个人倒了j毫升水的最大满意度
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++){//1-n个客人
ll a,b,c,d,e;cin>>a>>b>>c>>d>>e;
for(int j=0;j<=m;j++){//0-m毫升水
if(j<a)dp[i][j]=dp[i-1][j]+e;
else if(j>=a&&j<c)dp[i][j]=max(dp[i-1][j]+e,dp[i-1][j-a]+b);
else dp[i][j]=max(dp[i-1][j-a]+b,max(dp[i-1][j-c]+d,dp[i-1][j]+e));
}
}
cout<<dp[n][m];
return 0;
}
# 6、例题三：购物策略
n 件物品，有结算时间和自身价值，也可以买与不买，每 1 秒可以免费那其他物品，现在我们要花最少的钱，去买价值之和最多的物品们。
我们可以设置 dp[j]表示购买前 j 个物品所花费最少的钱。
状态转移方程:dp[j]=min(dp[j],dp[j-t[i]]+c[i]);
示例代码：*
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
ll dp[4005];// dp[j] 表示商品数量为j需要支付的最低金额
ll c[2005],t[2005];
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int n;cin>>n;
ll v=0;
for(int i=1;i<=n;i++){
cin>>t[i]>>c[i];// 时间，价值
t[i]++;// 1s可以拿一个商品，那么t[i]s可以拿t[i]个，包括子集，所以结算第i个物品 可以拿t[i]++个
v=max(v,t[i]);//统计所有物品结算时的最大的消费时间
}
v+=n;//免费的加上自己买的，v+n是可以拿到最大的物品数量
for(int i=1;i<=v;i++)dp[i]=1e18;//初始化，表示买不到
for(int i=1;i<=n;i++){
for(int j=v;j>=t[i];j--){
dp[j]=min(dp[j],dp[j-t[i]]+c[i]);//此件物品买与不买的判断
}
}
ll ans=1e16;
for(int i=n;i<=v;i++)ans=min(ans,dp[i]);
cout<<ans;
return 0;
}
# 完全背包
# 1、完全背包模型
完全背包又叫无穷背包，即每种物品有无数个背包。
有一个体积为 V 的背包，商店有 n 个物品，每个物品有一个价值 v 和体积 w，每个物品有无限多个，可以被拿无穷次，问能装下物品的最大价值。
设状态 dp[i]=max(dp[i],dp[i-w]+v) 表示 物品总体积为 i 的情况下的最大价值
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e4+5;
ll dp[N];
int n,M;
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>M;
for(int t=1;t<=n;t++){
int w,v;cin>>w>>v;
for(int i=w;i<=M;i++){
dp[i]=max(dp[i],dp[i-w]+v);
}
}
cout<<dp[M];
return 0;
}
# 例题 1：加训啦
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int A[1000009];//N名士兵
int B[509];//M个训练计划
int C[509];//每个训练计划消耗的精力
int dp[100009];//dp[i]表示获得至少i点力量所需要的最少精力
int N,M,K;
bool check(int mid)
{
ll ans=0;
for(int i=1;i<=N;i++)//枚举每个士兵的初始力量值
{
//若当前士兵的初始力量值小于mid，说明要消耗精力去训练他，使他获得mid-A[i]点力量
//同时累加训练该士兵所消耗的最少精力，即dp[mid-A[i]]
if(A[i]<mid)ans=ans+dp[mid-A[i]];
}
//累加完毕后检查所消耗的总精力是否超出K，若未超出说明该方案可行，否则不可行
if(ans<=K)return true;
else return false;
}
int main()
{
cin>>N>>M>>K;
for(int i=1;i<=N;i++)cin>>A[i];
for(int i=1;i<=M;i++)cin>>B[i];
for(int i=1;i<=M;i++)cin>>C[i];
memset(dp,0x3f,sizeof(dp));//dp数组先初始化为一个极大值，代表最少消耗的精力为无穷大，后续再缩小
dp[0]=0;//获得0点力量，无需消耗精力
for(int i=1;i<=M;i++)//依次考虑每个计划
{
for(int j=0;j<100009;j++)//枚举所有能获得的力量点数
{
//不选择当前计划，消耗的精力为dp[j]
//选择当前计划，若当前能获得的力量点数大于该计划的力量点数，则消耗的精力为dp[j-B[i]]+C[i]
//若当前能获得的力量点数不大于该计划的力量点数，则消耗的精力为dp[0]+C[i]
//二者取较小值，更新dp数组
dp[j]=min(dp[j],dp[max(0,j-B[i])]+C[i]);
}
}
//下面开始二分，枚举每个士兵所有可能获得的力量点数，找出下限值
//初始区间：最少获得1点力量，保险起见右端点可以选大一点
int left=1,right=100008;
while(left<=right)
{
int mid=(left+right)/2;//计算中间值
if(check(mid))left=mid+1;//若返回true，该方案可行，则取右半区间继续验证
else right=mid-1;//不可行，取左半区间继续验证
} //退出循环时left已经移至right右侧
if(check(left))cout<<left<<endl;//最后验证一遍left是否可行
else cout<<left-1<<endl;
return 0;
}