多维背包 hrbudt 1335 算法与追MM

hrbust
#include<string.h> //多进制储存数,第i位进制维back[i]+1,可以避免重复
#include<stdio.h>
using namespace std;
int vl[];
int w[];
int back[];
int v[][];
int c[];
int n,m;
int jinzhi[];
int main()
{
//freopen("input.txt","r",stdin);
int z,ok,now;
while(~scanf("%d%d",&n,&m))
{
memset(vl,,sizeof(vl));
for(int i=;i<m;i++){
scanf("%d",&back[i]);
}
for(int i=;i<n;i++){
scanf("%d",&w[i]);
for(int k=;k<m;k++){
scanf("%d",&v[i][k]);
}
}
jinzhi[]=;
z=;
for(int i=;i<m;i++){
jinzhi[i+]=jinzhi[i]*(back[i]+);
z+=back[i]*jinzhi[i];
}
for(int i=;i<n;i++)
{
c[i]=;
for(int k=;k<m;k++)
{
c[i]+=v[i][k]*jinzhi[k];
}
}
for(int i=;i<n;i++)
{
for(int k=z;k>=c[i];k--)
{
ok=;
now=k;
for(int j=;j<m;j++)
{
if(now%(back[j]+)<v[i][j])
{
ok=;
break;
}
else
now/=(back[j]+);
}
if(ok==)//printf("*");
if(vl[k]<vl[k-c[i]]+w[i])
vl[k]=vl[k-c[i]]+w[i];
}
}
printf("%d\n",vl[z]);
printf("%d \n",z);
for(int i=;i<n;i++)
printf("%d ",c[i]);
}
}
上一篇:也谈设计模式Facade


下一篇:php curl请求页面数据