题目大意
N件物品, 每件物品价值为a[i],数量为b[i], 问分成两堆差值尽量小.
解题思路
感觉像是多重背包的变形~~~
状态DP[N][V]表示,前i件物品,价值为V的方案数
转移方程
dp[i][ j+k*a[i] ] += dp[i-1][j] // k = 0..b[i]
#include<stdio.h> #include<stdlib.h> #include<string.h> const int N = 250010; int dp[2][N]; int main(){ int a[110], b[110], n; while( scanf("%d",&n) != EOF){ if( n < 0 ) break; memset( dp, 0, sizeof(dp)); dp[0][0] = 1; int V = 0; for(int i = 1; i <= n; i++){ scanf("%d%d",a+i,b+i); V += a[i]*b[i]; } for(int i = 1; i <= n; i++){ // 50 int cur = (i+1)&1, nxt = i&1; memset( dp[nxt], 0, sizeof(dp[nxt])); for(int j = 0; j <= V; j++){ // 250000 for(int k = 0; k <= b[i] && (k*a[i]+j)<=V; k++) //100 dp[nxt][ k*a[i]+j ] += dp[cur][j]; } } for(int i = V/2; i <= V; i++){ if( dp[n&1][i] ){ int ans = (i>V-i)?i:V-i; printf("%d %d\n", ans, V-ans ); break; } } } return 0; }