本文主要是介绍poj1276 多重背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如题：http://poj.org/problem?id=1276
Description
N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10
means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.
Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.
Notes:
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.
Input
cash N n1 D1 n2 D2 ... nN DN
where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.
Output
Sample Input
735 3 4 125 6 5 3 350 633 4 500 30 6 100 1 5 0 1 735 0 0 3 10 100 10 50 10 10
Sample Output
735 630 0 0
给出一个总价值，给出每一种物品的数量和价值，要求拼成最接近总价值但不超过总价值的策略的最大价值。
说白了就是背包的同时，当最终结果好过最大价值时，f[M]=最大价值。
然后输出就行，典型的多重背包。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define max(a,b)(a>b?a:b)
int f[100000+10];
int num[13];
int mon[13];
int N,M;
void CompletePack(int c,int w)
{
int j;
for(j=c;j<=M;j++)
{
f[j]=max(f[j],f[j-c]+w);
}
}
void ZeroOnePack(int c,int w)
{
int j;
for(j=M;j>=c;j--)
{
f[j]=max(f[j],f[j-c]+w);
}
}
void MultiplePack(int c,int w,int cnt)
{
if(c*cnt>=M)
{
CompletePack(c,w);
return;
}
int k=1;
while(k<cnt)
{
ZeroOnePack(k*c,k*w);
cnt-=k;
k*=2;
}
ZeroOnePack(cnt*c,cnt*w);
}
int main()
{
while(~scanf("%d",&M)&&M>=0)
{
int i;
scanf("%d",&N);
memset(f,0,sizeof(f));
for(i=1;i<=N;i++)
scanf("%d%d",&num[i],&mon[i]);
for(i=1;i<=N;i++)
MultiplePack(mon[i],mon[i],num[i]);
if(f[M]>M)
{f[M]=M;}
printf("%d\n",f[M]);
}
}
这篇关于poj1276 多重背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
