工商局网站实名认证怎么做,微信小程序用到的技术,学做网站用什么服务器,邵阳市住房和城乡建设局网站完全背包与01背包的区别 01背包对于一个物品只能选择一次#xff0c;但是完全背包可以选择任意次#xff1b; 思路 和01背包类似#xff0c;01背包我们只需要判断选或不选#xff0c;完全背包也是如此#xff0c;不同的是#xff0c;对于这个物品我们在判断选后在增加一…
完全背包与01背包的区别 01背包对于一个物品只能选择一次但是完全背包可以选择任意次 思路 和01背包类似01背包我们只需要判断选或不选完全背包也是如此不同的是对于这个物品我们在判断选后在增加一次选择的机会直到不选跳转至下一个物品即可 一般代码 f[i][j]max(f[i][j],f[i-1][j-k*v[i]]k*w[i]); 第k次不选的话就是它本身选的话就是直接选择k次即可 当然这个代码在数据稍微大一点的时候就会超出时间限制 #includeiostream
using namespace std;
const int N1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;cinnm;for(int i1;in;i){cinv[i]w[i];}for(int i1;in;i){for(int j0;jm;j){for(int k0;k*v[i]j;k){f[i][j]max(f[i][j],f[i-1][j-k*v[i]]k*w[i]);}}}coutf[n][m]endl;
}
优化思路 上面代码会超出时间限制是因为三层循环下面我们来把第三层循环优化掉 f[i][j]max(f[i][j],f[i-1][j-v]w,f[i-1][j-2*v]2*w,f[i-1][j-3*v]3*w......f[i-1][j-k*v]k*w) f[i][j-v]max( f[i][j-v],f[i-1][j-2*v]w,f[i-1][j-3*v]2*w......f[i-1][j-k*v]k*w) f[i-1][j-v]w,f[i-1][j-2*v]2*w,f[i-1][j-3*v]3*w......f[i-1][j-k*v]k*w 不就是f[i][j-v]w 那么我们可以得到f[i][j]max(f[i][j],f[i-1][j-v]w) 这样我们不就可以不用写第三层循环了吗 直接用 f[i][j]f[i-1][j]; if(jv[i]) f[i][j]max(f[i][j],f[i][j-v[i]]w[i]); 优化代码
#includeiostream
using namespace std;
const int N1004;
int f[N][N];
int w[N],v[N];int main()
{int n,m;cinnm;for(int i1;in;i){cinv[i]w[i];}for(int i1;in;i){for(int j0;jm;j){f[i][j]f[i-1][j];if(jv[i])f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);}}coutf[n][m]endl;
}
我们来看一下核心代码 f[i][j]f[i-1][j]; if(jv[i]) f[i][j]max(f[i][j],f[i][j-v[i]]w[i]); 还记得01背包的代码吗 f[i][j] f[i - 1][j]; if(jv[i]) f[i][j] max( f[i - 1][j],f[i - 1][j - v[i]] w[i] ); 是不是只有红色标记 f[i][j] max( f[i - 1][j],f[i - 1][j - v[i]] w[i] );不同 再次优化代码 注意 这里我的j的大小是从小到大开始的 01背包中f[i][j] max( f[i - 1][j],f[i - 1][j - v[i]] w[i] );对于f[j]就相当于f[i-1][j]的大小如果从小到大遍历那么f[i-1][j]的大小就会发现变化那么优化后的代码就不满足我们所推导的公式所以我们要从大到小 类比于01背包完全背包的公式 f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);对于这个公式如果从大到小就会改变f[i][j]的大小不满足所推导的公式 #includeiostream
#includecstring
using namespace std;
const int N1e4;
int f[N];
int w[N],v[N];int main()
{int n,m;cinnm;for(int i0;in;i)cinv[i]w[i];for(int i0;in;i){for(int jv[i];jm;j){f[j]max(f[j],f[j-v[i]]w[i]);}}coutf[m]endl;
}
以上就是全部内容
