剛開始一直在糾結怎麼記錄人數,因為一開始的想法是dp[i][j]表示前i個人是否能達j這個值,想過用狀態壓縮存儲路徑,然後發現狀態壓縮只適合在人數<20時,時間和空間復雜度才可以接受,也想過用數組存儲人數,但也不好操作,看了別人的解題報告,才發現自己想太多了,這裡根本不需要知道路徑,只需要知道到達j這個值時,有多少個人就可以了。所以直接加一個狀態表示人數,於是狀態就變成了:dp[i][k][j]表示前i 個人時,選k個人時,是否能到達j值
然後考慮到空間復雜度,省略i這個狀態,用逆序保證每個人只選一次
#include#include 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; }