赞
踩
@ 代码随想录算法训练营第7周(C语言)|Day42(动态规划)
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
bool canPartition(int* nums, int numsSize){ int target; int sum; sum=0; for(int i=0;i<numsSize;i++){ sum+=nums[i]; } if(sum%2!=0){ return false; } target=sum/2; int dp[target+1]; for(int i=0;i<target+1;i++){ dp[i]=0; } for(int i=0;i<numsSize;i++){ for(int j=target;j>=nums[i];j--){ dp[j]=dp[j]<(dp[j-nums[i]]+nums[i])?(dp[j-nums[i]]+nums[i]):dp[j]; } } return dp[target]==target; } // #include<stdio.h> // #include<string.h> // #define MAX(a,b) (((a)>(b))?(a):(b)) // #define ARR_SIZE(arr) ((sizeof((arr)))/sizeof((arr)[0])) // #define BAG_WEIGHT 4 // void test_back_pack(int *weights,int weightSize,int*values,int valueSize,int bagWeight){ // int dp[bagWeight+1]; // memset(dp,0,sizeof(int)*(bagWeight+1)); // for(int i=0;i<weightSize;i++){ // for( int j=bagWeight;j>=weights[i];--j){ // dp[j]=MAX(dp[j],dp[j-weights[i]]+values[i]); // } // } // printf("%d\n",dp[bagWeight]); // } // int main(int argc,char**argv){ // int weights[]={1,3.4}; // int values[]={15,20,30}; // test_back_pack(weights,ARR_SIZE(weights),values,ARR_SIZE(values),BAG_WEIGHT); // return 0; // }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。