#include #include #include using namespace std; #define MAXN 10 struct Goods_Info { int v; //价值 int w; //重量 double vw; //价值重量比 }goods[MAXN]; int n; int maxValue; bool solu[MAXN]; bool optimalSolu[MAXN]; bool Cmp(const Goods_Info a, const Goods_Info b) { return a.vw > b.vw; } //可装入一部分物品时,取得的最优价值 double Bound(int i, double v, int c) { //以物品的价值重量比递减将物品装入背包 while (i <= n && goods[i].w <= c) { v += goods[i].v; c -= goods[i].w; i++; } //将背包装满 if (i <= n) { v += (goods[i].vw * c); } return v; } void Backtrack(int k, int cv, int rc) { if (k > n) { if (cv > maxValue) { maxValue = cv; int i; for (i = 1; i <= n; i++) { optimalSolu[i] = solu[i]; } } } else { if (goods[k].w <= rc) //当前物品能否装入背包 { solu[k] = true; Backtrack(k+1, cv+goods[k].v, rc-goods[k].w); } if (Bound(k+1, cv, rc) > maxValue) //剩余物品的最优价值是否更优 { solu[k] = false; Backtrack(k+1, cv, rc); } } } int main(void) { int c; while (scanf("%d%d", &n, &c) != EOF) { int i; for (i = 1; i <= n; i++) { scanf("%d%d", &goods[i].v, &goods[i].w); goods[i].vw = (double)goods[i].v / goods[i].w; } //将物品按照价值重量比递减排序 sort(goods+1, goods+n+1, Cmp); maxValue = 0; Backtrack(1, 0, c); printf("%d\n", maxValue); //最优值 /* //最优解 printf("value:"); for (i = 1; i <= n; i++) { printf("\t%d", goods[i].v); } printf("\nweight:"); for (i = 1; i <= n; i++) { printf("\t%d", goods[i].w); } printf("\nstatus:"); for (i = 1; i <= n; i++) { printf("\t%d", optimalSolu[i]); } printf("\n"); */ } return 0; }
/*5 278 312 710 58 415 95 278 812 1210 108 815 155 268 812 1210 108 815 155 288 812 1210 108 815 155 298 812 1210 108 815 15*/