首页 > 代码库 > 多重背包
多重背包
//多重背包void WKnapsack4(int *value, int* v, int *Num, int n, int V){ int d[100][100]; memset(d, 0, sizeof(int)* 100*100); bool visit[100][100]; memset(visit, 0, sizeof(bool)* 100 * 100); int times[100][100]; memset(times, 0, sizeof(int)* 100 * 100); for (int i = 0; i < n; i++) { for (int j = v[i]; j <= V; j++) { for (int k = 0; k <= Num[i]; k++) { if (i == 0) { d[i][j] = 0; } else if(j >= k*v[i]) { if (d[i][j] < d[i - 1][j - k*v[i]] + k*value[i]) { visit[i][j] = true; times[i][j] = k; } d[i][j] = max(d[i][j], d[i - 1][j - k*v[i]] + k*value[i]); } } } } printf("%d ", d[n-1][V]); //多重背包,打印 printf("打印路径:\n"); for (int i = n - 1, j = V; i >= 0 && j>0; i--) { if (visit[i][j]) // { printf("value:%d num:%d\n",value[i], times[i][j]); j = j - v[i]; } }}
多重背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。