跳到主要内容

橱窗插画问题

橱窗插画问题

image-20201118151550527

image-20201118151940871

image-20201118152007640

image-20201118153711960

image-20201118154242087

枚举法​

#include <iostream>
using namespace std;

int V = 5;
int F = 3;

// 把num表示为二进制
void ToBinary(int num, int binary[])
{
  for(int i = 0; i < V; i++)
  {
    binary[i] = num & 1; // 取最低位
    num = num >> 1; // 右移一位
  }
}

// 计算V位二进制中1的个数
int Count1(int binary[])
{
  int count = 0;
  for(int i = 0; i < V; i++)
    count += binary[i];
  return count;
}

int main()
{
  void ToBinary(int num, int binary[]);
    int Count1(int binary[]);

// 定义美感方案
int beauty[V][F] = {
  {7, 5, -21},
  {23, 21, 5},
  {-5, -4, -4},
  {-24, 10, -20},
  {16, 23, 20},
};

// 定义最大美感得分和，相应方案
int best_beauty = 0, best_put = 0;

// 没劲0~2^V-1
for(int i = 0; i< (1<<V); i++)
{
  // 计算具体插花方案
  int binary[V] = {0};
  ToBinary(i, binary);
  if(Count1(binary) != F) // 不是合理方案
    continue;
  // 计算美感的分和
  int sum_beauty = 0;
  // 维护最大美感得分和，相应方案
  for(int vase = 0, flower = 0; vase < V; vase++)
    if(binary[vase] == 1) // 插了花
    {
      sum_beauty += beauty[vase][flower];
      flower++;
    }
  // 维护最大美感得分和、相应方案
  if(sum_beauty > best_beauty)
  {
    best_beauty = sum_beauty;
    best_put = i;
  }
}

// 输出答案
cout << "最大美感得分和" << best_beauty << endl;
cout << "相应方案：" ;
int best_binary[V] = {0};
ToBinary(best_put, best_binary);
for(int vase = 0, flower = 1; vase < V; vase++)
  if(best_binary[vase] == 1)
  {
    cout << flower;
    flower++;
  }
  else
  cout << 0;
}
// 最大美感得分和53
// 相应方案：01023

动态规划​

image-20201118170229300

image-20201118170748508

只要让最优部分插花方案的规模，从 1、2、。。。、V 个花瓶，并且一直保持最优，最终就能得到答案。

当最优部分插花方案的规模扩大（多考虑 1 个花瓶）时，有 2 种可能的最优方案：

新花瓶插花，或者新花瓶不插花

image-20201118171316985

#include <iostream>
using namespace std;

int V = 5;
int F = 3;

int main()
{
  void ToBinary(int num, int binary[]);
  int Count1(int binary[]);

  //定义美感数组
  int beauty[V][F] = {{7, 5, -21},
                      {23, 21, 5},
                      {-5, -4, -4},
                      {-24, 10, -20},
                      {16, 23, 20}};
  //定义最大美感得分和、相应方案
  int best_beauty = 0, best_put = 0;
  //枚举0 ~ 2^V - 1
  for (int i = 0; i < (1 << V); i++)
  {
    //计算具体插花方案
    int binary[V] = {0};
    ToBinary(i, binary);
    if (Count1(binary) != F) //不是合法方案
      continue;
    //计算美感得分和
    int sum_beauty = 0;
    for (int vase = 0, flower = 0; vase < V; vase++)
      if (binary[vase] == 1) //插了花
      {
        sum_beauty += beauty[vase][flower];
        flower++;
      }
    //测试代码
    //cout << "第" << i << "个sum_beauty = " << sum_beauty << endl;
    //维护最大美感得分和、相应方案
    if (sum_beauty > best_beauty)
    {
      best_beauty = sum_beauty;
      best_put = i;
    }
  }
  //输出答案
  cout << "最大美感得分和：" << best_beauty << endl;
  cout << "插花方法：";
  int best_binary[V] = {0};
  ToBinary(best_put, best_binary);
  for (int vase = 0, flower = 1; vase < V; vase++)
    if (best_binary[vase] == 1)
    {
      cout << flower;
      flower++;
    }
    else
      cout << 0;
  return 0;
}

void ToBinary(int num, int binary[])
{
  for (int i = 0; i < V; i++)
  {
    binary[i] = num & 1;
    num = num >> 1;
  }
}

int Count1(int binary[])
{
  int count = 0;
  for (int i = 0; i < V; i++)
    count += binary[i];
  return count;
}