大家好，又见面了，我是你们的朋友全栈君。
题目描述
小李对故乡的思念全部化作了对雾霾天气的怨念，这引起了掌控雾霾的邪神的极大不满，邪神派去了一只小怪兽去对付小李，由于这只怪兽拥有极高的IQ，它觉得直接消灭小李太没有难度了，它决定要和小李在智力水平上一较高下。我们可否帮助小李来战胜强大的怪兽呢？
问题是这样的：给定一堆正整数，要求你分成两堆，两堆数的和分别为S1和S2，谁分的方案使得S1*S1-S2*S2的结果小（规定S1>=S2），谁就将获得胜利。
注：S2可以等于0。
输入
第一行n（1<=n<=100），表示共有n个数
第二行共n个用空格隔开的正整数ai（ai<=100），表示给定的一堆正整数。
输出
输出就一个整数，表示 S1*S1-S2*S2 的最小值。
样例输入
4
1 2 3 4
样例输出
0
一开始根本没想到是背包问题，后来补题时慢慢想出来了（这小学组的题我做不来…..）
如题意：要把n个数分成两份，这两份尽可能接近
也就是说其中一份大于等于总和的一半，另一份小于等于，
然后我们看小于等于的那一份，
就是说要在n个数里找出m（m未知）个数使其和小于等于sum/2、且最大，自然剩余n-m个数的和大于等于sum/2、且最小
这两部分就最接近了，
关键就是找这m个数了，
这就等价与n个物品，sum/2的背包（价值与重量相等）
附上01背包模板代码
for(i = 0;i<n;i++)//n件物品
{
for(j = s ;j>=vi[i];j++)//背包容积
{
dp[j] = max(dp[j], dp[j-vi[i]]+wi[i]);//递推公式
}
}
Ac代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int main()
{
int dp[10000];
int a[1000];
int n,s=0;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i],s+=a[i];
for(int i=0;i<n;i++)
{
for(int j=s/2;j>=a[i];j--)
{
if(j>=a[i])
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
/*for(int j=0;j<=s/2;j++)
printf("%d\t",dp[j]);
printf("\n");*/
}
cout<<(s*(s-2*dp[s/2]))<<endl;
return 0;
}
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int dp[105][10000];
int main()
{
int a[105];
int n,s=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],s+=a[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=s/2;j++)
{
if(j>=a[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
else
dp[i][j]=dp[i-1][j];
}
}
cout<<(s*(s-2*dp[n][s/2]))<<endl;
return 0;
}
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/161548.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
