有没有做公司网站的,icp备案查询网官网,磁力猫引擎,坑梓网站建设哪家好分组背包是选不同的组#xff0c;每个组中只能选一个物品。分组背包就是01背包的变种#xff0c;多重背包就是特殊的分组背包。 //分组背包
#includeiostream
using namespace std;
const int N 110;
int f[N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(…分组背包是选不同的组每个组中只能选一个物品。分组背包就是01背包的变种多重背包就是特殊的分组背包。 //分组背包
#includeiostream
using namespace std;
const int N 110;
int f[N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin n m;for (int i 0; i n; i){int s; cin s;//初始化每组的数据for (int j 0; j s; j) cin v[j] w[j];for (int j m; j 0; --j){for (int k 0; k s; k){//这里必须加上判断因为这里j没有做限制if (j - v[k] 0) f[j] max(f[j], f[j - v[k]] w[k]);}}}cout f[m];return 0;
} 还有一种方法优化空间就是将物品放在外层循环
#include bits/stdc.husing namespace std;const int M 110;
int dp[M], last[M];
int N, V, S, v, w;int main()
{cin N V;for (int i 0; i N; i){cin S;for (int j 0; j S; j){cin v w;for (int k V; k v; k--)dp[k] max(dp[k], last[k - v] w);}memcpy(last, dp, sizeof dp);}cout dp[V] endl;return 0;
}每次last数组保存上一次的状态每个物品都会更新一次f[0]到f[V],如果不记录上一次的状态不需要加上if条件(循环k中已经加了限制了)就必须写成二维的数组了。这时就需要加上if条件了。优化掉的空间就是开数组的空间。
for(int i1;in;i){int s;scanf(%d,s);for(int k1;ks;k){//第i组第k个物品int a,b;scanf(%d%d,a,b);for(int jv;j0;j--){f[i][j]max(f[i][j],f[i-1][j]);if(ja) f[i][j]max(f[i][j],f[i-1][j-a]b);}}}一维数组无法取得上一层的状态 。
