链接:http://acm.hdu.edu.cn/showproblem.php?pid=1059
经典的多重背包问题,有若干个数,每个数可以取若干个,求问能不能取到总和的一半
直接把模板一敲就差不多了~
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int size = 600000;
int sum;
int dp[size];
void zeroOnePack(int cost,int weight)
{
int i;
for(i=sum;i>=cost;i--)
dp[i] = max(dp[i],dp[i-cost]+weight);
}
void completePack(int cost,int weight)......
阅读全文