»ØËÝ·¨½â¾öתÔØÎÊÌâ

»ð¼ýͲ¦î$¨|

#include <iostream.h>
const int MAX=10;
const int n=3;
const int i=1;
int w[]={10,40,40};
int cw=0,bestw=0,r=90,c=50;
int bestx[MAX],x[MAX];
int Backtrack(int i)
{
    if(i>n)
    {
        if(cw>bestw)//±ÈÉϴδó ¸üмǼ
        {
            for(int j=1;j<=n;j++)
                bestx[j]=x[j];
            bestw=cw;
        }
        return 0;
    }
    r-=w[i];
    if(cw+w[i]<=c)//ÄÜ×°Ï ËÑË÷×ó×ÓÊ÷
    {
        x[i]=1;
        cw+=w[i];
        Backtrack(i+1);
        cw-=w[i];
    }
    if(cw+r>bestw)//ËÑË÷ÓÒ×ÓÊ÷ ¼ÓÉÏʣϵıÈÏÖÔÚ×îÓŵĴ󣬿ÉÄÜÊÇ×îÓŽâ
    {
        x[i]=0;
        Backtrack(i+1);
    }
    r+=w[i];
}
int main()
{
    Backtrack(i);
    cout<<bestw<<endl;
    for(int i=0;i<MAX;i++)
        cout<<bestx[i];
    cout<<endl;
    return 0;
}

±àÒëÊÇÓиö¾¯¸æ£º¾ÍÊÇ˵²»ÊÇÿ¸öÖ´Ðз¾¶¶¼Óзµ»ØÖµ£¬µ«ÊǼÓÔÚBackTº¯Êý×îºóºó£¬½á¹û»¹ÊÇÒ»Ñù£¬Ó¦¸ÃÊÇ50²Å¶Ô°¡£¬ÔõôÊÇ40ÄØ

©a£¬

¾ÍÊÇ°Ñi¸³ÖµÎª0Âð

§°oË®Á÷Ó°ÔÚ.

³ÌÐò´úÂ룺
#include <iostream>
using namespace std;

const int MAX=10;
const int n=3;
//const int i=1;
int w[]={10,40,40};
int cw=0,bestw=0,r=90,c=50;
int bestx[MAX],x[MAX];
int Backtrack(int i)
{
        if(i>=n)
        {
                if(cw>bestw)
                {
                        for(int j=0;j<n;j++)
                                bestx[j]=x[j];
                        bestw=cw;
                }
                return 0;
        }
        r-=w[i];
        if(cw+w[i]<=c)
        {
                x[i]=1;
                cw+=w[i];
                Backtrack(i+1);
                cw-=w[i];
        }
        if(cw+r>bestw)
        {
                x[i]=0;
                Backtrack(i+1);
        }
        r+=w[i];
}
int main()
{
        Backtrack(0);
        cout<<bestw<<endl;
        for(int i=0;i<n;i++)
                cout<<bestx[i];
        cout<<endl;
        scanf("%*s");
        return 0;
}