本文主要是介绍poj2576(二维背包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：n个人分成两组，两组人数只差小于1 ， 并且体重只差最小
对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了
状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 105
#define inf 0x7fffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int c[N], dp[N/2][25000];int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int n;while(scanf("%d",&n) != EOF){int i, j, k;int sum = 0;for(i = 0 ; i < n; i++){scanf("%d",&c[i]);sum +=c[i];}memset(dp,0,sizeof(dp));int sum1 = sum/2, n1 = n/2;if(n&1) n1++;for(i = 1 ; i <= n1; i++)dp[i][0] = -inf;for(k = 0; k < n; k++)for(j = sum1; j >= c[k]; j--)for(i = n1; i >= 1; i--)dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);printf("%d %d\n",dp[n1][sum1],sum - dp[n1][sum1]);}return 0;
}
这篇关于poj2576(二维背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
