HDU 1171 杭电分设备（多重背包）
题意：给一组物品，要求分给A，B 2个人，要求A分到的价值总和不小于B，输出A，B分到的价值总和。
题解：多重背包问题：思路比较简单，设sum为物品的总价值
方法1：直接打背包价值的表F[V]（装满背包初始化为-INF），从v=sum/2往右找，满足F[v]>0的即可；
方法2：设背包容量为V=sum/2，直接找F[V]即可；
反思：当价值和容量是同一种的时候，基本都有2种方法，初始化为-INF，找满足条件下的因变量下对于的自变量x（什么样容量的背包可以被装满），
或初始化为0（这个背包最多可以装下的价值），找因变量；（把背包问题看成函数求最优解，x为定义域（容量），y为值域（价值总和等））；
方法1代码：
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int maxn=2e6+5; const int INF=0x3f3f3f3f; int f[maxn], c[maxn], w[maxn]; int main() { //freopen("in.txt", "r", stdin); int n; while (cin>>n, n>=0) { int all_n=1, sum=0; while(n--) { int val,num,k; cin>>val>>num; sum=sum+val*num; for(k=1; k<num; k<<=1){ w[all_n++]=k*val; num=num-k; } if(num) w[all_n++]=num*val; } for(int v=0; v<=sum; v++) f[v]=-INF; f[0]=0; for(int i=1; i<all_n; i++) for(int v=sum; v>=w[i]; v--) f[v]=max(f[v], f[v-w[i]]+w[i]); int tmp; if(sum%2) tmp=sum+1; else tmp=sum; int ans=0; for(int v=tmp/2; v>=0; v++) if(f[v]>0){ ans=v; break; } cout<<ans<<" "<<sum-ans<<endl; } return 0; }
方法2代码：
#include <cstdio> #include <iostream> #include <cstring> using namespace std; const int maxn=2e6+5; const int INF=0x3f3f3f3f; int f[maxn], c[maxn], w[maxn]; int main() { //freopen("in.txt", "r", stdin); int n; while (cin>>n, n>=0) { int all_n=1, sum=0; while(n--) { int val,num,k; cin>>val>>num; sum=sum+val*num; for(k=1; k<num; k<<=1){ w[all_n++]=k*val; num=num-k; } if(num) w[all_n++]=num*val; } memset(f, 0, sizeof(f)); for(int i=1; i<all_n; i++) for(int v=sum/2; v>=w[i]; v--) f[v]=max(f[v], f[v-w[i]]+w[i]); printf("%d %d\n", sum-f[sum/2], f[sum/2]); } return 0; }
原文：https://www.cnblogs.com/Yokel062/p/10686493.html