题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=565
题意很好理解，普通的01背包，dp[i - 1][j]表示在前i - 1件物品中选取若干物品放入容量为j背包所得到的最大的价值，dp[i - 1][j - w[i]] + v[i]表示前i - 1件物品中选取若干物品放入容量为j - w[i]背包所得到的最大的价值加上第i件物品的价值。这里同理，但是要记录选取的物品，觉得倒着过来就可以了。
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = ;
int dp[][MAXN] , v[];
vector <int> G;
int main()
{
ios::sync_with_stdio(false);
int V , n;
while(cin >> V >> n) {
G.clear();
for(int i = ; i <= n ; i++) {
cin >> v[i];
}
memset(dp , , sizeof(dp));
for(int i = ; i <= n ; i++) {
for(int j = ; j <= V ; j++) {
if(j < v[i])
dp[i][j] = dp[i - ][j];
else
dp[i][j] = max(dp[i - ][j] , dp[i - ][j - v[i]] + v[i]);
}
}
int i = n , j = V;
while(i > && j > ) {
if(j < v[i]) {
i--;
continue;
}
if(dp[i][j] == dp[i - ][j - v[i]] + v[i]) {
j -= v[i];
G.push_back(v[i]);
}
i--;
}
for(int i = G.size() - ; i > ; i--) {
cout << G[i] << " ";
}
cout << G[] << " sum:";
cout << dp[n][V] << endl;
}
}