思路

笔记

在 01 背包中，二维数组下，物品遍历和背包遍历顺序可以互换，滚动数组下，必须先遍历物品再遍历背包，并且背包从大到小遍历 滚动数组中，如果背包从小到大遍历，那么会导致前面的物品被放入多次 如果先遍历背包再遍历物品，那么每个背包只能放入一个物品

笔记

完全背包中，滚动数组下，物品遍历和背包遍历可以互换，背包遍历需要从小到大，因为物品可以添加多次

题目

HDU 1248

https://acm.hdu.edu.cn/showproblem.php?pid=1248

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 10010;

int dp[N];
int a[3] = {150, 200, 350};

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);

        memset(dp, 0, sizeof(dp));

        
        for(int i = 0; i < 3; i++){
            for(int j = 0; j <= n; j++){  // 遍历容量时，必须从小到大
                if(a[i] <= j){
                    dp[j] = max(dp[j], dp[j-a[i]]+a[i]);
                }
            }
        }
        printf("%d\n", n-dp[n]);
    }

    return 0;
}

参考链接