它要求的是每组物品至少选一个
创新互联致力于互联网网站建设与网站营销，提供成都网站建设、成都网站制作、网站开发、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
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);
?
#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;
}
