hdu 3591 多重背包+完全背包练习题

#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
int inf = 20001; //足够大的数
int v = 20000; //背包的容量
//处理一件01背包中的物品
void ZeroOnePack(int dp[], int cost, int weight)
{
for (int i = v; i >= cost; i--)//descend
dp[i] = min(dp[i], dp[i - cost] + weight);
}
//deal with one item
void CompletePack(int dp[], int cost, int weight)
{
for (int i = cost; i <= v; i++)
dp[i] = min(dp[i], dp[i - cost] + weight);
}
//deal with one item
void MultiplePack(int dp[], int cost, int weight, int number)
{
if (cost*number >= v) //注意等于号
{
//物品足够多转化为完全背包
CompletePack(dp, cost, weight);
return;
}
int k = 1;
while (k < number)//二进制拆分
{
ZeroOnePack(dp, k*cost, k*weight);
number -= k;
k << 2;
}
ZeroOnePack(dp, cost*number, weight*number);
}
int main(int)
{
int dp[20002], dp2[20002];//背包容量是钱的价值，重量是钱的数目(每个钱币的重量都是1)，求给出相同的钱的价值可以使用的最少（注意不是最大）的钱币数量
//But Xiaoqian is a low-pitched girl , she wouldn’t like giving out more than 20000 once.一次不会付钱超过20000块
int N, T, v[101], c[101], cnt = 0, i, j, ans;
while (scanf("%d %d", &N, &T) != EOF && (N != 0 || T != 0))
{
cnt++;
if (N == 0 || T == 0)
{
printf("Case %d: %dn", cnt, 0);
continue; //这里打成continue会卡在那里一直等待输入，报time limit exceeded
}
for (i = 1; i <= N; i++)
scanf("%d", &v[i]);
for (i = 1; i <= N; i++)
scanf("%d", &c[i]);
//初始化
for (i = 0; i<20002; i++)
dp[i] = inf, dp2[i] = inf;
//这里的初值只能设置为足够大，而不能是INT_MAX,否则dp[i - cost] + weight会由于溢出变成负数！！！
dp[0] = dp2[0] = 0; //注意dp[0]是有意义的，要单独初始化！！！
//背包
for (i = 1; i<=N; i++) //这里的上界应该是物品的数量
CompletePack(dp2, v[i], 1);
for (i = 1; i<=N; i++)//这里的上界应该是物品的数量
MultiplePack(dp, v[i], 1, c[i]);
ans = INT_MAX;
int t = inf;
for (i = T; i<20001; i++)
if (ans > dp[i] + dp2[i - T])
{
ans = dp[i] + dp2[i - T];
t = i;
}
!(dp[t] == inf || dp[t - T] == inf) ? printf("Case %d: %dn", cnt, ans) : printf("-1n");
}
return 0;
}
/**
3 70
5 25 50
5 2 1
0 0
**/