回溯法——01背包問題

[cpp] 
#include <iostream>  
#include <cstdio>  
#include <algorithm>  
 
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 27
8 3
12 7
10 5
8 4
15 9
 
5 27
8 8
12 12
10 10
8 8
15 15
 
5 26
8 8
12 12
10 10
8 8
15 15
 
5 28
8 8
12 12
10 10
8 8
15 15
 
5 29
8 8
12 12
10 10
8 8
15 15
*/