网站开发设计的技术,软件开发怎么自学,品牌建设口号,吉林企业网站建设https://codility.com/demo/take-sample-test/delta2011/ 0-1背包问题的应用。我自己一开始没想出来。“首先对数组做处理#xff0c;负数转换成对应正数#xff0c;零去掉#xff0c;计数排序统计有多少个不同元素及其对应个数#xff0c;并累加所有数的和sum#xff0c;… https://codility.com/demo/take-sample-test/delta2011/ 0-1背包问题的应用。我自己一开始没想出来。“首先对数组做处理负数转换成对应正数零去掉计数排序统计有多少个不同元素及其对应个数并累加所有数的和sum不妨记bsum/2不同元素个数为m则目标转换为在m个不同元素中挑出若干个元素每个元素可以重复多次但少于它们的出现次数使得它们的和不大于b并尽量接近。到了这里应该有点熟悉的感觉了吧。对了其实这就是0-1背包问题” 参考http://phiphy618.blogspot.jp/2013/05/codility-delta-2011-minabssum.html 第一次的代码并未完全通过75分大数据全挂。原因是这里一个元素可以出现多次是多重背包问题。 // you can also use imports, for example:
// import java.math.*;
class Solution {public int solution(int[] A) {// write your code here...if (A.length 0) return 0;int sum 0;int max 0;for (int i 0; i A.length; i) {if (A[i] 0) A[i] -A[i];sum A[i];}int target sum / 2;int dp[][] new int[A.length][target];for (int i 0; i A.length; i) {for (int j 0; j target; j) {// j1 is the weight limitif (i 0){if (A[i] (j1)) {dp[i][j] A[i];}else{dp[i][j] 0;}}else // i ! 0{int w1 dp[i-1][j];int w2 0;if (j-A[i] 0 ) {w2 dp[i][j-A[i]] A[i];}dp[i][j] w1 w2 ? w1 : w2;}}}max dp[A.length - 1][target - 1];return (sum - max * 2);}
}第二次参考了cp博士的文章处理了多重背包的优化并用了滚动数组http://blog.csdn.net/caopengcs/article/details/10028269 // you can also use includes, for example:
// #include algorithm
int solution(const vectorint A) {// write your code in C98int len A.size();int sum 0;int M 0;for (int i 0; i len; i) {int x 0;x A[i] 0 ? A[i] : -A[i];sum x;if (x M)M x;}vectorint count;count.resize(M1);for (int i 0; i len; i) {int x 0;x A[i] 0 ? A[i] : - A[i];count[x];}int target sum / 2;int largest 0;vectorint dp(target1, -1);for (int i 0; i M; i) {if (count[i] 0) {for (int j 0; j target; j) {if (j 0) dp[j] count[i];if (dp[j] 0) {dp[j] count[i];if (j largest)largest j;}else if (j - i 0 dp[j - i] 0) {dp[j] dp[j - i] - 1;if (j largest)largest j;}else {dp[j] -1;}}}}return abs(sum - 2 * largest);
}转载于:https://www.cnblogs.com/lautsie/p/3228644.html
