Problem Description A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply of nk bills. For example,
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 The program input is from standard input. Each data set in the input stands for a particular transaction and has the format: <br> <br>cash N n1 D1 n2 D2 ... nN DN <br> <br>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. <br>
Output For each set of data the program prints the result to the standard output on a separate line as shown in the examples below. <br>
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
多重背包模版題
每行資料第一個是要求價值 共有幾件物品, 第一件物品的個數,第一件物品的價值.....
要求找到能得到的距離要求最近的價值(不能比要求價值大)
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
int a[1000];
int t=0;
for(int i=0;i<m;i++)
{
int s1,v1;
scanf("%d %d",&s1,&v1);
for(int j=1;s1>0;j=j*2)
{
if(s1>=j)
s1=s1-j,a[t]=j*v1,t++;
else
a[t]=s1*v1,s1=0,t++;
}
}
int b[100010]={0};
int ma=0;
for(int i=0;i<t;i++)
{
for(int j=n;j>=a[i];j--)
b[j]=max(b[j],b[j-a[i]]+a[i]),ma=max(ma,b[j]);
}
printf("%d\n",ma);
}
return 0;
}