1A。看到直接A掉了还是很激动的呀啊啊。
思路简单，为了要尽量平分，就把总数取一半当做背包的容量，尽量取满就好。
今天下午的目标就是进阶完背包九讲。看了题目之后觉得是多重背包来着，但是有点懒得用多重背包，所以就没有优化，直接拿去一个一个找的，跑了一秒。。。待我再去领悟一番，再优化它。先上代码。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#define maxn 300000
int dp[maxn],val[51],num[51];
int main()
{
int n;
while(1)
{
scanf("%d",&n);
if(n<0) break;
memset(dp,0,sizeof(dp));
int i,j,k,sum=0;
for(i=1;i<=n;i++) {scanf("%d%d",&val[i],&num[i]);sum+=val[i]*num[i];}
int m=sum/2;
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
for(k=num[i];k>=0;k--)// for(k=0;k<=num[i];k++)
if(j>=k*val[i])
dp[j]=max(dp[j],dp[j-k*val[i]]+k*val[i]);
int ans[2];
ans[0]=dp[m];ans[1]=sum-dp[m];
sort(ans,ans+2);
printf("%d %d\n",ans[1],ans[0]);
}
return 0;
}
稍稍优化了一下，跑了七百多，，，，可是几十秒的是闹哪样啊！！。。。
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define maxn 300000
int que[maxn],dp[maxn];
int main()
{
int n,m;
while(1)
{
scanf("%d",&n);
if(n<0) break;
memset(dp,0,sizeof(dp));
int i,j,k,top=1,sum=0;
int val,num;
for(i=1;i<=n;i++)
{
scanf("%d%d",&val,&num);
for(j=1;j<=num;j++)
que[top++]=j*val;
sum+=val*num;
}
for(i=1;i<top;i++)
for(j=sum/2;j>=que[i];j--)
dp[j]=max(dp[j],dp[j-que[i]]+que[i]);
printf("%d %d\n",sum-dp[sum/2],dp[sum/2]);
}
return 0;
}
好吧，这里存在一个问题，就是多重背包好像不是这样优化的。。。。。或者说不止这样优化。
看背包九讲里面说，将每种类型物品的个数用二进制表示出来，就可以得到任意解。然后要注意公式，每个k都是要满足n-2^(k+1)>0，然后最后一个数是n减去前面几个k的和。这样就可以得到每个取法，而且也不会超出num[i]。多重背包提到说把完全背包和0-1背包结合（给了伪码），额，然后目前，我认为是把每个类型的物品用二进制处理后再用0-1背包处理。。。。
**************************************************
嗷，我知道为什么当某种物品的cost*num>vol的时候要用完全背包做了，因为这种情况就相当于你一直取它知道背包放不下，性质同完全背包。
好吧这么简答的东西当时没多想。。。。。
*************************************************
于是。。。。我按照这样的优化又写了一次，最终跑了一百秒。。。。然后注意sum不要乱除二！！原先我省事把sum直接除二了，然后算的时候再乘回去，尼玛哪里是一样的啊！wa死了。。。。然后学习那个二进制取数是怎么写的。。。
#include <stdio.h>
#include <string.h>
#define maxn 350000
int dp[maxn],que[maxn];
int max(int x,int y)
{
if(x>y) return x;
else return y;
}
int main()
{
int n;
while(1)
{
scanf("%d",&n);
if(n<0) break;
memset(dp,0,sizeof(dp));
memset(que,0,sizeof(que));
int i,j,k;
int val,num,top=1,sum=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&val,&num);
sum+=val*num;
for(k=1;k<=num;k<<=1)
{
que[top++]=k*val;
num-=k;
}
if(num>0)
que[top++]=num*val;
}
//for(i=1;i<top;i++) printf("**%d",que[i]);printf("\n");
for(i=1;i<=top-1;i++)
for(j=sum/2;j>=que[i];j--)
dp[j]=max(dp[j],dp[j-que[i]]+que[i]);
printf("%d %d\n",sum-dp[sum/2],dp[sum/2]);
}
return 0;
}
搜了一下题解，，看到跑的特别快的代码。。刚刚试了一下只有几十ms。。。。先贴着然后我自己领悟领悟
完全背包：
完全背包原先对于它取顺序的方法不是太理解，，或者说没大注意，，这里一看又有新理解了，正式因为顺序，所以你可以忽略它的件数，可以一直往里面取的。每次比较的时候都可能是上次已经取过的结果里面再取所得的结果。
但是这一题里面有点不解，应该可以直接归结于为什么这道题可以用完全背包做？。。。。。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[500005],w[1005];
int main()
{
int n,m;
while(cin>>n&&n>=0)
{
memset(dp,0,sizeof(dp));
int i,j,a,v_sum=0;
for(i=1;i<=n;++i)
{
cin>>w[i]>>a;
v_sum+=w[i]*a;
}
m=v_sum/2;
for(i=1;i<=n;++i)
{
for(j=w[i];j<=m;++j)
{
dp[j]=max(dp[j-w[i]]+w[i],dp[j]);
}
}
cout<<v_sum-dp[m]<<" "<<dp[m]<<endl;
}
}