Gym

题意：给你t和n，和n个ai，问你用最少的ai去装满t背包，如果有多个答案，输出最早出现的

思路：01背包问题，装与不装的问题，从t时间开始遍历下去，很容易得出答案

他的转移方程为：

dp[j] = dp[j - c[i]] + w[i];//表示在j-c[i]时间所得到的的贡献最大值

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define N 200005
#define INF 0x3f3f3f3f
#define M 1000000007
#define fori for(i=0;i<n;i++)
#define fori1 for(i=1;i<=n;i++)
ll c[N] = { 0 }, w[N];
bool path[55][N];//计算你已放进去的路径
ll dp[N];
int main()
{
    ll i, j, k;
    ll n, t;
    ll sum = 0, ret = 0, ret2 = 0;
    ll ans = 0;
    ll flag = 1;
    while (cin >> t)
    {
        memset(path, 0, sizeof(path));
        memset(dp, 0, sizeof(dp));
        if (t == 0)
            break;
        cin >> n;
        fori1
        {
            cin >> c[i];
        w[i] = c[i];
        }
        for (i = n; i >= 1; i--)
        {
            for (j = t; j >= c[i]; j--)
            {
                if (dp[j] <= dp[j - c[i]] + w[i])
                {
                    dp[j] = dp[j - c[i]] + w[i];
                    path[i][j] = 1;
                }
            }
        }
        for (i = 1, j = t; i <= n && j > 0; i++)
        {
            if (path[i][j])
            {
                cout << w[i] << " ";
                j -= c[i];

            }
        }
        cout << dp[t] << endl;
    }


}