背包问题--简化版和标准版

背包问题：

1、简化版：

输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。

拓展：给出一个数组，求数组中的数字组合使之为给定数字。

// 21题递归方法  
//copyright@ July && yansha  
//July、yansha，updated。  
#include<list>  
#include<iostream>  
using namespace std;  
  
list<int>list1;  
void find_factor(int sum, int n)   
{  
    // 递归出口  
    if(n <= 0 || sum <= 0)  
        return;  
      
    // 输出找到的结果  
    if(sum == n)  
    {  
        // 反转list  
        list1.reverse();  
        for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)  
            cout << *iter << " + ";  
        cout << n << endl;  
        list1.reverse();      
    }  
      
    list1.push_front(n);      //典型的01背包问题  
    find_factor(sum-n, n-1);   //放n，n-1个数填满sum-n  
    list1.pop_front();  
    find_factor(sum, n-1);     //不放n，n-1个数填满sum   
}  
  
int main()  
{  
    int sum, n;  
    cout << "请输入你要等于多少的数值sum:" << endl;  
    cin >> sum;  
    cout << "请输入你要从1.....n数列中取值的n：" << endl;  
    cin >> n;  
    cout << "所有可能的序列，如下：" << endl;  
    find_factor(sum,n);  
    return 0;  
}

2、标准版

在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求解这个背包能装的最大价值。（物体不能分割）。

#include <iostream>
#define MAX_NUM 5
#define MAX_WEIGHT 10
using namespace std;

//动态规划求解
int zero_one_pack(int total_weight, int w[], int v[], int flag[], int n) {
  int c[MAX_NUM+1][MAX_WEIGHT+1] = {0}; //c[i][j]表示前i个物体放入容量为j的背包获得的最大价值
  // c[i][j] = max{c[i-1][j], c[i-1][j-w[i]]+v[i]}
  //第i件物品要么放，要么不放
  //如果第i件物品不放的话,就相当于求前i-1件物体放入容量为j的背包获得的最大价值
  //如果第i件物品放进去的话,就相当于求前i-1件物体放入容量为j-w[i]的背包获得的最大价值
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= total_weight; j++) {
      if (w[i] > j) {
        // 说明第i件物品大于背包的重量，放不进去
        c[i][j] = c[i-1][j];
      } else {
        //说明第i件物品的重量小于背包的重量，所以可以选择第i件物品放还是不放
          if (c[i-1][j] > v[i]+c[i-1][j-w[i]]) {
            c[i][j] = c[i-1][j];
          }
          else {
            c[i][j] =  v[i] + c[i-1][j-w[i]];
          }
      }
    }
  }

  //下面求解哪个物品应该放进背包
  int i = n, j = total_weight;
  while (c[i][j] != 0) {
    if (c[i-1][j-w[i]]+v[i] == c[i][j]) {
      // 如果第i个物体在背包，那么显然去掉这个物品之后，前面i-1个物体在重量为j-w[i]的背包下价值是最大的
      flag[i] = 1;
      j -= w[i];
      //--i; 移到外面去
    }--i;
  }
  return c[n][total_weight];
}

//回溯法求解
int main() {
  int total_weight = 10;
  int w[4] = {0, 3, 4, 5};
  int v[4] = {0, 4, 5, 6};
  int flag[4]; //flag[i][j]表示在容量为j的时候是否将第i件物品放入背包
  int total_value = zero_one_pack(total_weight, w, v, flag, 3);
  cout << "需要放入的物品如下" << endl;
  for (int i = 1; i <= 3; i++) {
    if (flag[i] == 1)
      cout << i << "重量为" << w[i] << ", 价值为" << v[i] << endl;
  }
  cout << "总的价值为: " << total_value << endl;
  return 0;
}