//题目//有N件物品和一个容量为W的背包。//第i件物品的重量是w[i]，价值是v[i]。//求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。//基本思路//这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。//用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：//f[i][v] = max{ f[i - 1][v], f[i - 1][v - w[i]] + v[i] }。//可以压缩空间，f[v] = max{ f[v], f[v - w[i]] + v[i] }//将前i件物品放入容量为v的背包中，若只考虑第i件物品的策略（放或不放），//那么就可以转化为一个只牵扯前i - 1件物品的问题。如果不放第i件物品，//那么问题就转化为“前i - 1件物品放入容量为v的背包中”，//价值为f[i - 1][v]；如果放第i件物品，//那么问题就转化为“前i - 1件物品放入剩下的容量为v - w[i]的背包中”，//此时能获得的最大价值就是f[i - 1][v - w[i]]再加上通过放入第i件物品获得的价值v[i]。#include
     
        #include
      
       #include 
       
        using namespace std;void show(vector
        
         
          > &res_table)//显示二阶矩阵{    for (int i = 0; i < res_table.size(); i++)    {        for (int j = 0; j < res_table[i].size(); j++)            cout << res_table[i][j] << ' ';        cout << endl;    }}void packege_0_1(vector
          
           
            > &res_table, vector
            
              &thing_weight, vector
             
               &thing_value){ for (int i = 0; i < res_table[0].size(); i++)//得到放入的第一个物品后的最优值 { if (i < thing_weight[0]) res_table[0][i] = 0; else res_table[0][i] = thing_value[0]; } for (int i = 1; i < res_table.size(); i++)//得到放入后面的(n - 1)物品后的最优值 { for (int j = 0; j < res_table[i].size(); j++) { if (thing_weight[i] > j) res_table[i][j] = res_table[i - 1][j]; else { res_table[i][j] = (res_table[i - 1][j] >(res_table[i - 1][j - thing_weight[i]] + thing_value[i])) ? res_table[i - 1][j]:(res_table[i - 1][j - thing_weight[i]] + thing_value[i]); } } }}int getres(vector
              
               
                > &res_table){ return res_table[res_table.size() - 1][res_table[0].size() - 1];}int main(){ int package_weight = 0, count = 0;//package_weight-背包容量, count-物品数量 vector
                
                  thing_weight,thing_value;// thing_weight - 每个物品的质量,thing_value - 每个物品的价格 cin >> package_weight >> count; int temp = count; while (temp--) { int number_temp, value_temp; cin >> number_temp >> value_temp; thing_weight.push_back(number_temp); thing_value.push_back(value_temp); } vector
                 
                  
                   > res_table(count, vector
                   
                    (package_weight+1));//二阶矩阵用于存储最优解 show(res_table); cout << endl; cout << endl; packege_0_1(res_table, thing_weight, thing_value); show(res_table); cout <<"The result is : "<< getres(res_table) << endl; system("pause");}