剛開(kāi)始一直在糾結(jié)怎么記錄人數(shù)，因?yàn)橐婚_(kāi)始的想法是dp[i][j]表示前i個(gè)人是否能達(dá)j這個(gè)值，想過(guò)用狀態(tài)壓縮存儲(chǔ)路徑，然后發(fā)現(xiàn)狀態(tài)壓縮只適合在人數(shù)<20時(shí)，時(shí)間和空間復(fù)雜度才可以接受，也想過(guò)用數(shù)組存儲(chǔ)人數(shù)，但也不好操作，看了別人的解題報(bào)告，才發(fā)現(xiàn)自己想太多了，這里根本不需要知道路徑，只需要知道到達(dá)j這個(gè)值時(shí)，有多少個(gè)人就可以了，

POJ 2576 Tug of War

。所以直接加一個(gè)狀態(tài)表示人數(shù)，于是狀態(tài)就變成了：dp[i][k][j]表示前i 個(gè)人時(shí)，選k個(gè)人時(shí)，是否能到達(dá)j值

    然后考慮到空間復(fù)雜度，省略i這個(gè)狀態(tài)，用逆序保證每個(gè)人只選一次

#include<stdio.h>#include<string.h>int dp[105][45005],w[105];int n;void init(){	memset(dp,0,sizeof(dp));	dp[0][0]=1;}int main(){	#ifndef ONLINE_JUDGE	freopen("in.txt","r",stdin);	#endif	scanf("%d",&n);	int sum=0;	for(int i=1;i<=n;i++) {		scanf("%d",&w[i]);		sum+=w[i];	}	init();	for(int i=1;i<=n;i++){		for(int j=sum;j-w[i]>=0;j--){			for(int k=n/2+1;k>=1;k--){				if(dp[k-1][j-w[i]]) {					dp[k][j]=dp[k-1][j-w[i]];				}			}		}	}	for(int i=sum/2;i>=0;i--){		if(n&1) {			if(dp[n/2][i]||dp[n/2+1][i]) {				printf("%d %d\n",i,sum-i);				break;			}		}		else{			if(dp[n/2][i]) {				printf("%d %d\n",i,sum-i);				break;			}		}	}	return 0;}</string.h></stdio.h>