首页 > 代码库 > poj1170 - 转换成背包
poj1170 - 转换成背包
题目链接
有5种物品,给出每个物品的单价。
给出几个这些物品的组合和这个组合的价格。买组合要比一件件的买便宜。
问给定的购买计划最少花多少钱。
------------------------------------------------------------------------------------------------
因为最多有5种,可以用一个5位数表示状态。
然后就是完全背包了。f[v]为状态v的最小花费。注意初始状态为f[0]=0;其余为无穷大。
#include <set> #include <map> #include <stack> #include <queue> #include <cmath> #include <vector> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b)) #define MIN(a,b) ((a)<=(b)?(a):(b)) #define long long LL #define OO 0x0fffffff using namespace std; const int N = 128; int f[66666]; int cost[N],value[N]; int mapp[1024]; bool cmp(int a,int b){ for(int i=0;i<5;i++){ int tb = b%10; if( tb > 5 ) return false; if((a%10)>tb) return false; a/=10; b/=10; } return true; } int main(){ int m,n,t,code,cnt,goal; goal = 0; cin>>m; for(int i=0;i<m;i++){ cin>>code>>cnt>>cost[i]; mapp[code] = i; value[i] = pow(10,i); goal += cnt*value[i]; } cin>>n; n += m; for(int i=m;i<n;i++){ value[i] = 0; cin>>t; while(t--){ cin>>code>>cnt; value[i]+=(int)pow(10,mapp[code])*cnt; } cin>>cost[i]; } for(int i=1;i<goal+8;i++) f[i]=OO; f[0]=0; for(int i=0;i<n;i++){ for(int v=value[i];v<=goal;v++){ if(cmp(value[i],v)){ f[v] = MIN(f[v],f[v-value[i]]+cost[i]); } } } printf("%d\n",f[goal]); return 0; }
poj1170 - 转换成背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。