php背包数据 php 数据分析 包

对于杭电acm 3033 http://acm.hdu.edu.cn/showproblem.php?pid=3033 这个分组背包的至少怎么处理呀，详细

它要求的是每组物品至少选一个

创新互联致力于互联网网站建设与网站营销，提供成都网站建设、成都网站制作、网站开发、seo优化、网站排名、互联网营销、微信小程序、公众号商城、等建站开发，创新互联网站建设策划专家，为不同类型的客户提供良好的互联网应用定制解决方案，帮助客户在新的全球化互联网环境中保持优势。

这里我的办法可能有点啰嗦

令f[i][j]表示前i组中选择价钱为j的方案的最佳价值

则该状态满足最优子结构且无后效性 能想通就行了吧

初始化f[k][j]=-1(k!=0) 0(k==0) {因为这里初始化为-1 所以状态转移的时候只能从上个品牌转移过来 这样就达到至少选一个的效果了 不知道懂没有}

状态方程f[k][j]=maxx(f[k][j],f[k-1][j-w[i]]+v[i],f[k][j-w[i]]+v[i])

其中第i件物品属于第k组

解释起来也很简单

要么是上个品牌+该品牌 要么是该品牌选多个

这样就一定能保证每组都至少要选一个

因为除了f[0][i]其它都赋值的是-1，所以一定能够有前一组的转移过来 除非条件不够 就输出Impossible

输出Impossible还有个条件 就是组数的最大数还

这题我犯了个错误 对其理解还不是很透

类似PHP的背包问题，谢谢

你看一下是想要这样的结果吗？

?php 

function my_rand($min,$max,$num){

$re=array();

while(count($re)$num){

$tem=mt_rand($min,$max);

if(!in_array($tem,$re)){$re[]=$tem;}

}

return $re;

}

function my_try($arr,$arr1){

$keys=my_rand(0,4,mt_rand(2,3));

$count=0;

$out=array();

foreach($keys as $v){

$count+=$arr[$v];

$out[$arr1[$v]]=$arr[$v];

}

if($count==1000){echo "pre";var_dump($out);echo "br";}else{echo $count,"br";}

}

$arr=array(500,100,400,200,300);

$arr1=array(1,2,3,4,5);

my_try($arr,$arr1);

?

完全背包问题http://acm.hdu.edu.cn/showproblem.php?pid=1114

#includeiostream

using namespace std;

int max(int a,int b)

{

a=ab?a:b;

return a;

}

int Knapsack(int n,int c,int w[],int v[],int x[])

{

int i,j;

int a[n+1][c+1];

for(i=0;i=n;i++)a[i][0]=0;//初始化第0列

for(j=0;j=c;j++)a[0][j]=0;//初始化第0行

for(i=1;i=n;i++)//计算第i行，进行第i次迭代

for(j=1;j=c;j++)

if(jw[i]) a[i][j]=a[i-1][j];

else a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+v[i]);

j=c;//求装入背包的物品

for(i=n;i0;i--)

{

if(a[i][j]a[i-1][j])

{

x[i]=1;

j=j-w[i];

}

else x[i]=0;

}

return a[n][c];//返回最大值

}

int main()

{

int n=5,c=10,x[n];

int w[6]={0,2,2,6,5,4};//w[]数组和v[]数组分别装物品重量和对应的价值，由于函数问题，w[0]和v[0]必须装0，或改动函数也可以不必这样

int v[6]={0,6,3,5,4,6};

n=Knapsack(n,c,w,v,x);

coutnendl;

system("pause");

return 0;

}