首页 > 代码库 > 1007 正整数分组
1007 正整数分组
0_1背包问题的变形,这是第一次的错解:DP时把每个物品体积设置为1,导致漏了一些结果。
#include<iostream> #include<algorithm> #include<cstdio> #include<iomanip> #include<cmath> #include<vector> #include<string> using namespace std; typedef long long LL; #define M 1000000007 int a[105]; int dp[105][105]; int main() { int t,sum=0; scanf("%d",&t); for(int i=0;i<t;i++) { scanf("%d",&a[i]); sum+=a[i]; } int m=M,aim,cnt=1,temp=sum; while(temp%10==0) { cnt*=10; temp/=10; } aim = temp/2*cnt; sort(a,a+t); for(int i=0;i<t;i++) { if(i==0) dp[0][1] = a[i]; else { dp[i][0] = dp[i-1][0]; for(int j=1;j<=t;j++) { dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+a[i]); if(dp[i][j]-aim>=0) m = min(m,dp[i][j]-aim); } } } // 150 75 15 sum-aim-m int M1 = max(sum-aim-m,aim+m),M2 = min(sum-aim-m,aim+m); printf("%d",M1-M2); return 0; }
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int N=105; int n,a[N],Sum,Su,dp[N*100]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),Sum+=a[i]; Su=Sum/2; for(int i=1;i<=n;i++){ for(int j=Su;j>=a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]+a[i]); } printf("%d\n",Sum-2*dp[Su]); return 0; }
1007 正整数分组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。