PAT-A-1068

1. A1068

1.1. 题目

1.2. 样例输入&&样例输出

1.3. 思路

0 1背包问题，是你最爱的动态规划
XD动态规划看了就有点害怕，不过学了还是能理解一些的
关于动态规划1还有2能帮助你理解一些动态规划背包问题

1.4. AC代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int w[10004], dp[103] = { 0 };
bool flag[10004] = { false };
bool choice[10004][103] = { false };
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    sort(w + 1, w + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        for (int v = m; v >= w[i]; v--) {
            if (dp[v] <= dp[v - w[i]] + w[i]) { //如果放入i 
                dp[v] = dp[v - w[i]] + w[i];
                choice[i][v] = true;
            }
        }
    }
    if (dp[m] != m)
        puts("No Solution");
    else {
        int k = n, num = 0, v = m;
        while (k > 0) {
            if (choice[k][v] == true) {
                flag[k] = true;
                v -= w[k];
                num++;
            }
            k--;
        }
        for (int i = n; i >= 1; i--) {
            if (flag[i]) {
                printf("%d", w[i]);
                num--;
                if (num > 0) putchar(' ');
            }
        }
    }
    return 0;
}