1. Toy模板网首页
  2. > Toy博客

【DP】学习之背包问题

8月前 作者：想七想八不如11408 分类：Toy博客 阅读(46) 违法举报

这篇具有很好参考价值的文章主要介绍了【DP】学习之背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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;
}

 这里补个图，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个物品开始，选总体积<=j的物品的总价值的最大值 
	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个物品中选，选总体积<=j的物品的总价值的最大值 
	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;
}

空间优化递推

用一维数组代替二维数组 

【DP】学习之背包问题

#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;
}

进一步优化

这里m从m走到0，的原因是只让每个物品最多拿一次。

如果正序枚举体积，就会让物品被拿多次，从而违反规则，

但完全背包不用考虑这个问题，因为它本身就能拿多次~

所以完全背包优化到一维可以正序枚举。

#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;
}

二维费用背包问题(本质是01背包）

8. 二维费用的背包问题 - 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;
}

正序+二维优化

#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背包唯一不同就在于如果当前这个物品可以装入，在下一次选择中x不用+1（因为物品是无限多的，还可以再次选择）

#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;
}

优化成一维数组 

#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   背包优化到一维      ：逆序枚举体积

完全背包优化到一维      ：正序枚举体积

习题

云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

NASA的食物计划（二维费用背包问题）

P1507 NASA的食物计划 - 洛谷 | 计算机科学教育新生态 (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;
}

优化后的二维数组递推

#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的方案数

278. 数字组合 - AcWing题库

记忆化搜索

 Time Limit Exceeded   

要优化成递推

#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;
}

一维数组递推

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int a[N];
int f[10010];//记录方案数 
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的方案数

OpenJudge - 6049:买书

记忆化搜索

这个就能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;
}

优化一下

#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])
		//如果可以选并且选了之后方案数会变多 
    	{
    		cout<<i<<" ";//那就选择 
    		j-=v[i];//体积减少 
    		i++;
		}
		else i++;
	}
    return 0; 
}

采药

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (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;
}

优化后

#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 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

没别的，这题要注意数据范围 

#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倍经验日

P1802 5 倍经验日 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

仔细读题 

#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:宠物小精灵之收服文章来源地址https://www.toymoban.com/news/detail-435358.html

#include <bits/stdc++.h>
using namespace std;
int dp[1005][505];//dp[i][j][k]:
//(第一维i被优化掉）前i个野生小精灵中最多使用j个精灵球，
//k点皮卡丘的体力值，能捕捉到的最大小精灵数量。 
int b[105], d[105];//b[i]:收第i小精灵需要的精灵球球数 
//d[i]:收第i小精灵皮卡丘损失的体力值 
int main()
{
    int n, m, ka, r;
    cin >> n >> m >> ka;//n个精灵球 皮卡丘m点体力值 野生小精灵有ka个 
    m--;//不能把m点体力值都用完，最多可以使用m-1点体力 
    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);//记录精灵球个数 
                
    for(int k = 0; k <= m; ++k)//用掉的体力值可以为0，从0开始遍历 
    {
        if(dp[n][k] == dp[n][m])//d[n][m]收服的数量肯定是最多的 
        {//一旦前面有一个跟dp[n][m]收服的数量相同，就更新答案 
            r = m + 1 - k ;//原总体力值为m+1，减去用掉的体力j 
            break;
        }   
    }
    cout << dp[n][m] << ' ' << r;
    return 0; 
}

到了这里，关于【DP】学习之背包问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 动态规划DP之背包问题3---多重背包问题

    动态规划DP之背包问题3---多重背包问题

    目录 DP分析： 优化：  二进制优化 例题：         01背包是每个物品只有一个，完全背包问题是每个物品有无限个。         那么多重背包问题就是 每个物品有有限个 。 有 N 种物品和一个容量是 V 的背包。 第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。 求解

    2024年03月20日
    浏览(35)
  • 【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    【算法|动态规划 | 01背包问题No.2】AcWing 423. 采药

    个人主页：兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助 🍓希望我们一起努力、成

    2024年02月06日
    浏览(34)
  • AcWing算法提高课-1.3.11二维费用的背包问题

    AcWing算法提高课-1.3.11二维费用的背包问题

    点这里 题目描述 有 N N N 件物品和一个容量是 V V V 的背包，背包能承受的最大重量是 M M M 。 每件物品只能用一次。体积是 v i v_i v i ​ ，重量是 m i m_i m i ​ ，价值是 w i w_i w i ​ 。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大

    2024年02月06日
    浏览(37)

  • C++ DP算法，动态规划——背包问题（背包九讲）

    有N件物品和一个容量为 V V V 的背包。放入第i件物品耗费的空间是 C i C_i C i ​ ，得到的价值是 W i W_i W i ​ 。 求解将哪些物品装入背包可使价值总和最大。 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即 F [ i , v ] F[i, v] F

    2024年02月16日
    浏览(37)
  • 【算法宇宙——在故事中学算法】背包dp之完全背包问题

    【算法宇宙——在故事中学算法】背包dp之完全背包问题

    学习者不灵丝相传，而自杖明月相反，子来此事却无得失。 尽管计算机是门严谨的学科，但正因为严谨，所以要有趣味才能看得下去。在笔者的前几篇算法类文章中，都采用了以小故事作为引入的方式来介绍算法，但在回看的时候发现学术味还是太浓了，完全没有想看下去的

    2023年04月20日
    浏览(42)
  • DP算法应用：背包问题解析与实现

    DP算法应用：背包问题解析与实现

    通过详细解析背包问题的动态规划解法，包括状态设计、状态转移方程、两种编码方法（自顶向下和自下而上），以及滚动数组的优化，帮助理解和实现动态规划算法。

    2023年04月08日
    浏览(25)
  • 【第二十五课】动态规划：完全背包问题(acwing-3 / 公式推导 / 思路理解 / 优化 / c++代码)

    【第二十五课】动态规划：完全背包问题(acwing-3 / 公式推导 / 思路理解 / 优化 / c++代码)

    目录 思路 朴素代码 优化 公式推导上  二维代码  一维代码 公式理解上   在开始看完全背包问题之前，可能需要先了解01背包及其解决办法。 指路👇 【第二十五课】动态规划：01背包问题(acwing-2 / 思路 / 含一维数组优化 / c++代码) 这个问题和01背包的区别就是 每件物品可以

    2024年03月19日
    浏览(51)

  • 算法第十五期——动态规划(DP)之各种背包问题

    目录 0、背包问题分类 1、 0/1背包简化版 【代码】 2、0/ 1背包的方案数 【思路】

    2023年04月09日
    浏览(31)
  • 【算法设计与分析基础(第三版)习题答案】8.2 背包问题和记忆功能

    【算法设计与分析基础(第三版)习题答案】8.2 背包问题和记忆功能

    a. 对于下列背包问题的实例，应用自底向上动态规划算法求解。 b. a 中的实例有多少不同的最优子集 c. 一般来说，如何从动态规划算法所生成的表中判断出背包问题的实例是不是具有不止一个最优子集？ 承重量 W = 6 物品 重量 价值 1 3 25 2 2 20 3 1 15 4 4 40 5 5 50 题目中要求使用

    2023年04月08日
    浏览(30)
  • 0-1背包问题思路分析，重点解释一维dp数组的01背包问题为什么要倒序遍历背包，以及为什么不能先遍历背包，只能先遍历物品

    0-1背包问题思路分析，重点解释一维dp数组的01背包问题为什么要倒序遍历背包，以及为什么不能先遍历背包，只能先遍历物品

    对0-1背包问题的二维dp数组以及一维dp数组的思路分析 来源：代码随想录 link 本文是我对01背包问题的理解 ，在本文中具体分析dp数组的形成过程，最核心的地方就是我对每种情况下的01背包问题给出了代码运行结果，便于读者理解。 重点解释了为什么一维dp数组的01背包问题

    2024年02月03日
    浏览(78)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包