三种解法:多重背包转化为完全背包和01背包;多重背包通过二进制化化为01背包;通过计数法优化为2重循环。
code1:
47MS
#include <cstdio>
#include <cstring>
#define Max(a,b) (a) >(b)?(a):(b)
int dp[100005], Cost[11], Count[11], cash;
void ZeroOnePack(int cost)
{
int i;
for(i=cash; i>=cost; --i)
dp[i] = Max(dp[i], dp[i-cost]+cost);
}
void CompletePack(int cost)
{
int i;
for(i=cost; i<=cash; ++i)
dp[i] = Max(dp[i], dp[i-cost]+cost)......
阅读全文