题意:给6种不同币值的钱,求从【1,100】各个值用最少的硬币组成这些值
例如
1 2 5 10 20 50
68=50+20-1-1 四个
思路:多次完全背包或(加钱完全背包一次,再找零背包一次),ps:背包的大小不是100,应该2000左右(因为可以找零
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define CL(a,b) memset(a,b,sizeof(a))
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
#define INF 0x7ffffff
using namespace std;
const int M(2000);
int ff[M],a[10];
int main()
{
int t,i,j,k;
scanf("%d",&t);
while(t--)
{
for(i=0;i<6;i++)
scanf("%d",&a[i]);
for(i=0;i<M;i++)
ff[i]=INF;
ff[0]=0;
for(k=0;k<15;k++)//多次完全背包,15次就可以过这题
{
for(i=0;i<6;i++)
{
for(j=0;j<M;j++)
{
if(j-a[i]>=0)
ff[j]=MIN(ff[j-a[i]]+1,ff[j]);
if(j+a[i]<M)
ff[j]=MIN(ff[j+a[i]]+1,ff[j]);
}
}
}
/*
for(i=0;i<6;i++) // 两次背包
{for(j=0;j<M;j++){if(j-a[i]>=0)ff[j]=MIN(ff[j-a[i]]+1,ff[j]);}}for(i=0;i<6;i++)for(j=M-1;j>=0;j--)if(j+a[i]<M)ff[j]=MIN(ff[j+a[i]]+1,ff[j]);*///printf("\n");int sum=0,maxm=0;for(i=0;i<101;i++){sum+=ff[i];// printf("(%d,%d) ",i,ff[i]);maxm=MAX(maxm,ff[i]);}//
printf("\n");printf("%.2lf %d\n",(double)sum/100.0,maxm);}}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
poj 1001答案
北大POJ2002-Squares 解题报告+AC代码
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告