chapter 16 贪心算法

1.活动选择问题

16.1-1 运用动态规划解决活动安排问题

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 16/03/20.
//  Copyright © 2016年 YangKi. All rights reserved.

#include <cstdio>
#include <iostream>

#define Num 11 //the num of activity

using namespace std;
int s[Num+2]={0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 16};
int f[Num+2]={0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16, 17};
int c[Num+2][Num+2];// sij 代表在ai结束之后，aj开始之前的活动集合,c[i][j]表示sij的最大相互兼容的活动子集的个数
int subset[Num+2][Num+2];

void activity_arrange()
{
    for (int i=0; i < Num+1; i++)
        c[i][i+1] = 0;
    
    for (int i=0; i < Num+2; i++)
    {
        for (int j=0; j < Num+2; j++)
        {
            subset[i][j]=-1;
        }
    }
    
    for (int j=2; j<=Num+1; j++)
    {
        for (int i=j-2; i>=0; i--)
        {
            //get c[i][j]
            int temp=0;
            for (int k=i+1; k<j; k++)
            {
                if (s[k]>=f[i] && f[k]<=s[j])
                {
                    if (c[i][k]+c[k][j]+1 > temp)
                    {
                        temp = c[i][k]+c[k][j]+1;
                        subset[i][j]=k;
                    }
                }
            }
            c[i][j]=temp;
        }
    }
}


void print_sub(int i, int j)
{
    if (subset[i][j] != -1)
    {
        printf("a_%d\n", subset[i][j]);
        print_sub(i, subset[i][j]);
        print_sub(subset[i][j], j);
    }
}

int main()
{
    activity_arrange();
    printf("num:%d\n", c[0][Num+1]);

    print_sub(0, Num+1);
    return 0;
}

2.贪心算法原理

16.2-1 0-1背包问题

基本的

//  main.cpp
// 
//  Created by YangKi on 16/03/21.
//  Copyright © 2016年 YangKi. All rights reserved.
//  0-1背包问题
#include <cstdio>
#include <iostream>
#define Num 3 //the num of goods
#define Volume 50 // the volume of bag
using namespace std;
int w[Num+1]={50, 10, 20, 30};
int v[Num+1]={0, 60, 100, 120};
int c[Num+1][Volume+1]; //c[i][j]表示到第i个商品为止，总重量为j的范围内，能够得到的最大的价值，c[Num][Volume]就是答案

void zero_one_pack()
{
    for (int i = 0; i <= Num; ++i)
    {
        for (int j = 0; j < w[i]; ++j)
            c[i][j]=0;
    }

    c[0][Volume]=0;

    for (int i = 1; i <= Num; ++i)
    {
        for (int j = w[i]; j <= Volume; ++j)//j>= w[i],否则根本连第i个都放不下，更不用提前i个的情况
        {
            if (w[i] <= Volume)
            {
                if (c[i-1][j] < c[i-1][j-w[i]]+v[i])
                {
                  c[i][j] = c[i-1][j-w[i]]+v[i];
                  printf("c[%d][%d]=c[%d][%d-%d]+v[%d]\n", i, j, i-1, j, w[i], i);
                }
                else
                {
                    c[i][j] = c[i-1][j];
                    printf("c[%d][%d]=c[%d][%d]\n", i, j, i-1, j);
                }
            }
            else//包放不下该物品
            {
                c[i][j]=c[i-1][j];//肯定不放了
            }
        }
    }
}

int main()
{
    zero_one_pack();
    printf("result:%d\n", c[Num][Volume]);

    return 0;
}

优化了空间的, 注意里面的遍历方向

//  main.cpp
// 
//  Created by YangKi on 16/03/21.
//  Copyright © 2016年 YangKi. All rights reserved.
//  0-1背包问题
#include <cstdio>
#include <iostream>
#define Num 3 //the num of goods
#define Volume 50 // the volume of bag
using namespace std;
int w[Num+1]={50, 10, 20, 30};
int v[Num+1]={0, 60, 100, 120};
int c[Volume+1]; 

void zero_one_pack()
{
    for (int i = 0; i <= Volume; ++i)
        c[i]=0;

    for (int i = 1; i <= Num; ++i)
    {
        for (int j = Volume; j >= w[i]; --j)//!!!!!!!!!!!!!!!!!!
        {
            if (c[j] < c[j-w[i]]+v[i])
                {
                    c[j] = c[j-w[i]]+v[i];
                    printf("c[%d]=c[%d-%d]+v[%d]\n", j, j, w[i], i);
                }
        }
    }
}

int main()
{
    zero_one_pack();
    printf("result:%d\n", c[Volume]);

    return 0;
}