题目链接：

题意很好理解，普通的01背包，dp[i - 1][j]表示在前i - 1件物品中选取若干物品放入容量为j背包所得到的最大的价值，dp[i - 1][j - w[i]] + v[i]表示前i - 1件物品中选取若干物品放入容量为j - w[i]背包所得到的最大的价值加上第i件物品的价值。这里同理，但是要记录选取的物品，觉得倒着过来就可以了。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int MAXN = 130005; 6 int dp[30][MAXN] , v[30]; 7 vector 
        
          G; 8 int main()  9 {10     ios::sync_with_stdio(false);11     int V , n;12     while(cin >> V >> n) {13         G.clear();14         for(int i = 1 ; i <= n ; i++) {15             cin >> v[i];16         }17         memset(dp , 0 , sizeof(dp));18         for(int i = 1 ; i <= n ; i++) {19             for(int j = 0 ; j <= V ; j++) {20                 if(j < v[i])21                     dp[i][j] = dp[i - 1][j];22                 else23                     dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - v[i]] + v[i]);24             }25         }26         int i = n , j = V;27         while(i > 0 && j > 0) {28             if(j < v[i]) {29                 i--;30                 continue;31             }32             if(dp[i][j] == dp[i - 1][j - v[i]] + v[i]) {33                 j -= v[i];34                 G.push_back(v[i]);35             }36             i--;37         }38         for(int i = G.size() - 1 ; i > 0 ; i--) {39             cout << G[i] << " ";40         }41         cout << G[0] << " sum:";42         cout << dp[n][V] << endl;43     }44 }