http://poj.org/problem?id=2576
二维数组01背包的变形。
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 8147 | Accepted: 2191 |
Description
Input
Output
Sample Input
3 100 90 200
Sample Output
190 200
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 |
#include<iostream>#include<cstdio>#include<cstring>using
namespace std; int weight[120],sum,sum1,dp[50000][103];int Max(int
x,int y){ if(x>y) return
x; else return
y;}int
main(){ int
n,i,n1,j,k; while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); sum=0; for(i=1;i<=n;i++) { cin>>weight[i]; sum+=weight[i]; } dp[0][0]=1; sum1=sum/2; n1=(n+1)/2; for(i=1;i<=n;i++) for(j=sum;j>=weight[i];j--) for(k=n1;k>0;k--) if(dp[j-weight[i]][k-1]) dp[j][k]=1; for(i=sum1;i>=0;i--) if(dp[i][n1]||dp[i][n1-1]) break; cout<<i<<" "<<sum-i<<endl; } return
0;} |
HDU-2576 Tug of War,布布扣,bubuko.com
原文：http://www.cnblogs.com/cancangood/p/3590744.html