当前位置: 首页> 文旅> 艺术 > 微信小程序开发_如何做一个属于自己的网站_百度视频广告怎么投放_潍坊网站建设平台

微信小程序开发_如何做一个属于自己的网站_百度视频广告怎么投放_潍坊网站建设平台

时间:2025/7/11 14:19:56来源:https://blog.csdn.net/2301_81772249/article/details/146886683 浏览次数:1次
微信小程序开发_如何做一个属于自己的网站_百度视频广告怎么投放_潍坊网站建设平台

其实这个完全背包的步骤和01背包也是差不多滴,不过他有一些优化是我们必须要说一说的

老样子,我们先定义一下状态表示

step1: f[i][j]表示从1到i个物品里选出体积不超过j的最大价值

step2:状态转移方程

写成一行就是

我们再写一下f[i][j-v[i]]的表达式

可以推出f[i][j]其实就是等于max(f[i-1][j],f[i][j-v[i]+w[i])

这就是我们优化后的状态转移方程,很简单

step3:初始化,全部初始化为0

step4:结果就存在f[n][V]里

#include <iostream>
using namespace std;
const int N = 1010;
int n,V;
int v[N],w[N];
int f[N][N];
int main()
{cin >> n >> V;for(int i = 1;i<=n;i++){cin >> v[i] >>  w[i];}for(int i = 1;i<=n;i++){for(int j = 0;j<=V;j++){f[i][j] = f[i-1][j];if(j>=v[i]){f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);}}}cout << f[n][V] << endl;return 0;
}

嗯,我们还需要想一想这个代码怎么进行空间优化可以看到,我们更新一维数组的时候,我们需要当前位置和左边位置的元素,所以我们必须得先把左边位置更新出来才行,所以我们必须从左往右更新才正确

优化代码

#include <iostream>
using namespace std;
const int N = 1010;
int n,V;
int v[N],w[N];
int f[N];
int main()
{cin >> n >> V;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<=V;j++){f[j] = max(f[j],f[j-v[i]]+w[i]);}}cout << f[V];return 0;
}

好的好的,那我们来继续做一下第二问

step1:定义状态表示 f[i][j]表示的是从1到i个物品里选出恰好体积为j的物品的最大价值

step2:定义状态表示,和上面的一样

step3:初始化,全部初始化为负无穷,因为我们要用到max,不能让坏值影响我们的推导

并单独把f[0][0]设置为0

step4:答案如果存在的话就存在f[n][V]

#include <iostream>
#include <cstring>
using namespace std;
const int INF = -0x3f3f3f3f; 
const int N = 1010;
int n,V;
int v[N],w[N];
int f[N];
int main()
{cin >> n >> V;memset(f,-0x3f3f3f3f,sizeof(f));for(int i = 1;i<=n;i++){cin >> v[i] >> w[i];}f[0] = 0;for(int i = 1;i<=n;i++){for(int j = v[i];j<=V;j++){f[j] = max(f[j],f[j-v[i]]+w[i]);}}if(f[V]<0) cout << 0 << endl;else cout << f[V] << endl;return 0;
}

关键字:微信小程序开发_如何做一个属于自己的网站_百度视频广告怎么投放_潍坊网站建设平台

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: