ACM_物品分堆（01背包）

物品分堆

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

有n个物品，物品i的重量为Wi，现在想要把这个n个物品分类两堆，求最小的重量差（物品不可分割）。

Input:

输入包含多组测试，每组测试第一行输入一个整数n(1≤n≤100);第二行输入n个整数Wi(1≤ai≤10^4)。

Output:

对于每组测试，输出一个数字，表示分成两堆后的最小质量差。

Sample Input:

5

2 3 5 23 35

5

10 7 8 6 11

Sample Output:

2

0
解题思路：简单的01背包，每个物品只有一件，将所有物品的重量相加sum后取一半sum/2作为背包的容量，那么问题转化成从n件物品中挑选出若干件物品，使得其总重量不超过sum/2时有最大价值（最大重量），即典型的01背包，因为sum-dp[sum/2]>=dp[sum/2]，所以最后两堆物品之差为sum-2*dp[sum/2]。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 int n,sum,wi[],dp[];//数组长度开10^6+5

 int main(){

     while(~scanf("%d",&n)){

         sum=;

         memset(dp,,sizeof(dp));

         for(int i=;i<n;++i){

             scanf("%d",&wi[i]);

             sum+=wi[i];

         }

         for(int i=;i<n;++i)

             for(int j=sum/;j>=wi[i];--j)//01背包

                 dp[j]=max(dp[j],dp[j-wi[i]]+wi[i]);

         printf("%d\n",sum-*dp[sum/]);//两堆物品重量之差

     }

     return ;

 }

巴特西

ACM_物品分堆（01背包）

物品分堆

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章