poj-1170 (状态压缩形式下的完全背包)

 #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int b=;//进制
int B[];
int mapp[];// id 映射
int val[];// 价值
int cost[];// 花费
int dp[];//状态下的最小花费
int n,m,goal;// goal 最终的状态
bool cmp (int x,int y) {
for (int i=;i<n;i++) {
int tx=x%b;
int ty=y%b;
if (tx<ty) return false;
x/=b;
y/=b;
}
return true;
}
int main ()
{
ios::sync_with_stdio(false);
B[]=;
for (int i=;i<=;i++) B[i]=B[i-]*b;
cin>>n;
for (int i=;i<n;i++) {// 单价也看做是一种更新方案
int id,num;
cin>>id>>num>>val[i];
mapp[id]=i;
cost[i]=B[i];// i 从0开始
goal+=cost[i]*num;
}
cin>>m;
for (int i=n;i<n+m;i++) {
int t; cin>>t;
int state=;
for (int j=;j<=t;j++) {
int id,num;
cin>>id>>num;
state+=cost[mapp[id]]*num;
}
cost[i]=state;// 优惠方案的cost
cin>>val[i];
}
memset (dp,0x3f,sizeof(dp)); dp[]=;
for (int i=;i<n+m;i++)
for (int j=cost[i];j<=goal;j++) {
if (cmp (j,cost[i]))// 更新的时候 判断各个物品是否大于cost[i](能否更新)
dp[j]=min (dp[j],dp[j-cost[i]]+val[i]);
}
cout<<dp[goal]<<endl;
return ;
}
上一篇:利用CSS3新特性实现完全兼容的自定义滚动条。


下一篇:win7下Arduino Mega 2560驱动安装失败解决办法