UVA562 Dividing coins 动态规划 - c++编程基础

一道动态规划，不是很复杂，想到了处理写起来很简单，想不到还是毫无头绪的，给你n个钱币，并给出这些钱币的面值，尽量把它们按照总面值平分成两堆，求两堆钱币的总面值的差的绝对值

刚开始看到毫无思路，找不到边界值，不知道设DP数组，状态转移也找不出来，后来想到了用背包来解决，这些钱币的总值我们知道，所以我们可以把钱币总值作为背包容量，将钱币放入背包中，但是dp数组不是用来记录当前背包容量的，dp[i]无非两个值：0，1，0表示用这些钱币来组成总值为i的一堆是不行的，1表示可以，这样我们全部处理一遍，然后从这些钱币总值的一半开始往下找，找到的第一个就是符合题目要求的，那么差就好求了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[50000 + 12]; int coin[112]; void clear() { memset(dp,0,sizeof(dp)); memset(coin,0,sizeof(coin)); } int main() { int t; int n; cin>>t; while(t--) { clear(); cin>>n; int sum = 0; for(int i=0;i
                    
                     >coin[i]; sum += coin[i]; } int mid = sum/2; dp[0] = 1; for(int i=0;i
                     
                      =coin[i];j--) if(dp[j - coin[i]]) dp[j] = 1; } int mark; for(int i=mid;i>=0;i--) { if(dp[i] == 1) { mark = i; break; } } int ans = sum - mark*2; cout<