#include "stdafx.h"

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>

typedef float T;


T c;	//背包容量
int n;	//物品數
T *w;	//物品重量
T *p;	//物品價值
T cw;	//當前重量
T cp;	//當前價值
int *choose;	//當前裝載情況
T bestp;	//最優價值
int *bestc;	//最優裝載情況
#define  MAXNUM   100

//回溯法
void backtrack(int t)
{
	int i,j;
	if(t>n)
	{
		for(i=1;i<=n;i++)
		{
			cout<<choose[i]<<" ";
		}
		cout<<cw<<" ";
		cout<<cp<<endl;
		if(cp>bestp)
		{
			bestp=cp;
			for(j=1;j<=n;j++)
			{
				bestc[j]=choose[j];
			}
		}
	}
	else
	{
		for(i=0;i<=1;i++)
		{
			if(i==0)
			{
				choose[t]=0;
				backtrack(t+1);
			}
			if(i==1 && cw+w[t]<=c)
			{
				cw+=w[t];
				cp+=p[t];
				choose[t]=1;
				backtrack(t+1);
			}
		}
	}
	cw-=w[t-1]*choose[t-1];
	cp-=p[t-1]*choose[t-1];
}

//貪心法
void greedy()
{


	int index=1,max=0;
	int *temp;
	temp=new int[n+1];
	for(int i=1;i<=n;i++)
	{
		choose[i]=0;
		cw=0;
		cp=0;
	}
	for(int j=1;j<=n;j++)
	{
		for(i=1;i<=n;i++)
		{
			if((p[j]/w[j])<(p[i]/w[i]))
			{
				index++;
			}

		}
		temp[j]=index;
		index=1;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(temp[j]==i)
			{
				if(w[j]<c)
				{
					choose[j]=1;
					c-=w[j];
					cw+=w[j];
					cp+=p[j];
				}
			}
		}
	}
	
	bestp=cp;
	for(i=1;i<=n;i++)
	{
		bestc[i]=choose[i];
	}
}

struct node
{
    int step;
    T price;
    T weight;
    T max, min;
    unsigned long po;
};

typedef struct node DataType;

struct  SeqQueue 
{        /* 順序隊列類型定義 */
    int  f, r;
    DataType  q[MAXNUM];
};

typedef  struct SeqQueue *PSeqQueue;    


PSeqQueue createEmptyQueue_seq( void ) 
{  
    PSeqQueue paqu;
    paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu == NULL)
        printf("Out of space!! \n");
    else 
        paqu->f = paqu->r = 0;

    return paqu;
}

int  isEmptyQueue_seq( PSeqQueue paqu ) {
    return paqu->f == paqu->r;
}

// 在隊列中插入一元素x 
void  enQueue_seq( PSeqQueue paqu, DataType x ) {
    if( (paqu->r + 1) % MAXNUM == paqu->f  )
        printf( "Full queue.\n" );
    else {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r + 1) % MAXNUM;
    }
}

// 刪除隊列頭元素
void  deQueue_seq( PSeqQueue paqu ) {
    if( paqu->f == paqu->r )
        printf( "Empty Queue.\n" );
    else
        paqu->f = (paqu->f + 1) % MAXNUM;
}

// 對非空隊列,求隊列頭部元素
DataType  frontQueue_seq( PSeqQueue paqu ) 
{
    return (paqu->q[paqu->f]);
}

// 求最大可能值
T up(int k, T m, int n, T p[], T w[]){
    int i = k;
    T s = 0;
    while (i < n && w[i] < m) {
        m -= w[i];
        s += p[i];
        i++;
    }
    if (i < n && m > 0) {
        s += p[i] * m / w[i];
        i++;
    }
    return s;
}

// 求最小可能值
T down(int k, T m, int n, T p[], T w[]){
    int i = k;
    T s = 0;
    while (i < n && w[i] <= m) {
        m -= w[i];
        s += p[i];
        i++;
    }
    return s;
}

// 用隊列實現分支定界算法
T solve(T m, int n, T p[], T w[], unsigned long* po)
{
    T min;
    PSeqQueue q = createEmptyQueue_seq();
    DataType x = {0,0,0,0,0,0};
    x.max = up(0, m, n, p, w);
    x.min = min = down(0, m, n, p, w);
    if (min == 0) return -1;
    enQueue_seq(q, x);
    while (!isEmptyQueue_seq(q))   
	{
        int step;
        DataType y;
        x = frontQueue_seq(q);
        deQueue_seq(q);
        if (x.max < min) continue;
        step = x.step + 1;
        if (step == n+1) continue;
        y.max = x.price + up(step, m - x.weight, n, p, w);
        if (y.max >= min) 
		{
            y.min = x.price + down(step, m-x.weight, n, p, w);
            y.price = x.price;
            y.weight = x.weight;
            y.step = step;
            y.po = x.po << 1;
            if (y.min >= min) 
			{
                min = y.min;
                if (step == n) 
				{
					*po = y.po;
				}
            }
            enQueue_seq(q, y);
        }
        if (x.weight + w[step-1] <= m) 
		{
            y.max = x.price + p[step-1]+up(step, m-x.weight-w[step-1], n, p, w);
            if (y.max >= min) 
			{
                y.min = x.price + p[step-1]+down(step, m-x.weight-w[step-1], n, p, w);
                y.price = x.price + p[step-1];
                y.weight = x.weight + w[step-1];
                y.step = step;
                y.po = (x.po << 1) + 1;
                if (y.min >= min) 
				{
                    min = y.min;
                    if (step == n) 
					{
						*po = y.po;
					}
				}
                enQueue_seq(q, y);
            }
        }
    }
    return min;
}

//分支限界法
void fzjx()
{
	T d;
    unsigned long po;
    d = solve(c, n, &p[1], &w[1], &po);
    if (d == -1)
	{
        printf("No solution!\n");
	}
    else 
	{
        for (int i = 0; i < n; i++)
		{
			bestc[i+1]=((po & (1<<(n-i-1))) != 0);
		}
		bestp=d;
    }
}

void Traceback(int n,T w[],T v[],T p[][2],int *head,int x[])
{
	T j=p[head[0]-1][0],
	m=p[head[0]-1][1];
	for(int i=1;i<=n;i++)
	{
		x[i]=0;
		for(int k=head[i+1];k<=head[i]-1;k++)
		{
			if(p[k][0]+w[i]==j && p[k][1]+v[i]==m)
			{
				x[i]=1;
				j=p[k][0];
				m=p[k][1];
				break;
			}
		}
	}
}

T Knapsack(int n,T c,T v[],T w[],T p[][2],int x[])
{
	int *head=new int[n+2];
	head[n+1]=0;
	p[0][0]=0;
	p[0][1]=0;
	int left=0,right=0,next=1;
	head[n]=1;

	for(int i=n;i>=1;i--)
	{
		int k=left;
		for(int j=left;j<=right;j++)
		{
			if(p[j][0]+w[i]>c) break;
			T y=p[j][0]+w[i],
			m=p[j][1]+v[i];
			while(k<=right && p[k][0]<y)
			{
				p[next][0]=p[k][0];
				p[next][1]=p[k][1];
				next++;
				k++;
			}
			if(k<=right && p[k][0]==y)
			{
				if(m<p[k][1]) m=p[k][1];
				k++;
			}
			if(m>p[next-1][1])
			{
				p[next][0]=y;
				p[next][1]=m;
				next++;
			}
			while(k<=right && p[k][1]<=p[next-1][1])
			{
				k++;
			}
		}
		while(k<=right)
		{
			p[next][0]=p[k][0];
			p[next][1]=p[k][1];
			next++;k++;
		}
		left=right+1;
		right=next-1;
		head[i-1]=next;
	}
	Traceback(n,w,v,p,head,x);
	return p[next-1][1];
}

//動態規劃
void dtgh()
{
	T o[65536][2];
    bestp=Knapsack(n,c,p,w,o,bestc);
}