Question

01背包问题

能不能用性价比来做呢
动态规划看不懂啊

Answer 1

能不能用性价比来做呢
动态规划看不懂啊
----------------------------------------------------------------------
如果不是0-1问题的话，当然可以通过比较性价比来做，这时候可考虑用贪心算法；但如果是0-1问题的话就不能单纯“用性价比来做”了，因为有可能背包空出一大块。举个简单的例子：一个背包的容量是10KG，
物品A重7KG，价值为14元，
物品B重6KG，价值为11元，
物品C中4KG，价值为7元，
从性价比来看，A最高，但是将A放到背包里以后，无法放进其他物品了，此时总价值为14元；显然，本问题的最佳方案为将B、C放入背包，总价值为18元。

这就是0-1背包问题为什么能用动态规划算法，而不能用贪心算法的原因。共同学习:-D

Answer 2

背包问题的一个c语言递归算法如下，程序不长在win-tc和Dev-c++下试验通过，但要可能要举实例对着程序操作才可以完全理解。
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
struct Bag
{ int weight;
int value;
}Bag[MAX];
int a[MAX];
int Value=0;
int Weight;
int comb(int m,int k)
{int i,j;
int wei,val;
for(i=m;i>=k;i--)
{ a[k]=i;
if(k>1)
comb(i-1,k-1);
else
{ wei=0; /* 预值0 */
val=0;
for(j=a[0];j>0;j--) /* 每一种组合求它们的重量和价值 */
{ wei=wei+Bag[a[j]].weight;
val=val+Bag[a[j]].value;
}
if(wei<=Weight&&val>Value) /* 判断是否满足条件进行赋值 */
Value=val;
}
}
return Value;
}
void main()
{ int num,subnum;
int l,
clrscr();
printf("\n输入背包的总个数:"); /* 输入背包的总个数 */
scanf("%d",&num);
printf("输入背包的重量和价值\n",num); /* 输入背包的重量和价值 */
for(l=1;l<=num;l++)
scanf("%d,%d",&Bag[l].weight,&Bag[l].value);
printf("输入满足要求背包的个数:\n"); /* 输入满足要求背包的个数 */
scanf("%d",&subnum);
printf("输入满足条件的重量:\n",subnum); /* 输入满足条件的重量*/
scanf("%d",&Weight);
a[0]=subnum;
printf("the max value is:%d",comb(num,subnum));
getch();
}

Answer 3

可以利用价格体积比来近似求解，效果也很好，但是最优结果最好还是用动态规划算法来

Answer 4

性价比做的话就成贪心了，很容易举出反例的，
网上有个资料叫“背包9讲”，是信息学奥林匹克的教材，不过写的不错，可以去看下