刚才的标签对齐那片文章提到的关于调整两行之间的长度差的问题。0-1背包问题解决这个问题就很简单了：用其中的一些尽量去放满一半的总容量就好了。比较麻烦的一个问题是如何记录能达到最优情况的时候两行里面分别是什么？这个问题其实也是挺简单的，具体看下面的代码吧。
#include
#include
#include
#include #define MAX_NUM 40
#define MAX_LEN 40
#define MAX_CAP 2000 int len[MAX_NUM]; void init();
void solve(); int main(){ init(); solve();
} void init(){ int i, j; srand(1); for(i = 0; i < MAX_NUM; i++){ len[i] = rand()%MAX_LEN + 1; } for(i = 0; i < MAX_NUM; i++){ printf("%d ", len[i]); } printf("\n");
} void solve(){ int dp[MAX_CAP], total = 0, i, j; for(i = 0; i < MAX_NUM; i++){ total += len[i]; } total = (total+1)/2; memset(dp, -1, sizeof(dp)); dp[0] = 0; for(i = 0; i < MAX_NUM; i++){ for(j = total; j >= 0; j--){ if(dp[j] != -1 && len[i]+j <= total && dp[j+len[i]] == -1){ dp[j+len[i]] = j; } } } for(i = total; i >= 0 && dp[i] == -1; i--); bool used[MAX_NUM]; memset(used, false, sizeof(used)); printf("第一组：\n"); while(i > 0){ for(j = MAX_NUM-1; j >= 0 && i > 0; j--){ if(used[j] == false && len[j] == i-dp[i]){ used[j] = true; printf("(%2d,%2d)\n", j, len[j]); i = dp[i]; } } } printf("\n第二组：\n"); for(i = 0; i < MAX_NUM; i++){ if(used[i] == false){ printf("(%2d,%2d)\n",i, len[i]); } } printf("\n"); total = 0; for(i = 0; i < MAX_NUM; i++){ if(used[i] == true) total += len[i]; } printf("%d ", total); for(i = total = 0; i < MAX_NUM; i++){ if(used[i] == false) total += len[i]; } printf("%d\n", total);
}
这个过程还是挺简单的哈。
-------------------------------
欢迎拍砖。
延伸阅读
最新评论