# 1981. Minimize the Difference Between Target and Chosen Elements
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Knapsack Problem`
Link: https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/
## 思路
背包问题
但如果用传统方法解 会发现时间复杂度有```80*80*4900```那么高 (因为最多有70组，每个物品最多是70，最终总容量的可能性是```70*70=4900```，所以每一个回合需要遍历4900种容量，并且与下一组的70个物品两两组合。总共70个回合)
优化方法是在每个回合当中如果遇到比target大的值 我们只保留所有比target大的值里面最小的那个(因为现在比target大 之后只会和target越差越远)
所以时间复杂度变成了```70*70*801```
## Code
java

class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        int n = mat.length;
        int m = mat[0].length;
        Set<Integer> set = new HashSet<>();
        set.add(0);
        
        for(int i=1; i<=n; i++){
            Set<Integer> temp = new HashSet<>();
            int greater = -1;
            for(int j=0; j<m; j++){
                for(int k:set){
                    if(k+mat[i-1][j]<=target){
                        temp.add(k+mat[i-1][j]);
                    }
                    else{
                        if(greater==-1) greater = k+mat[i-1][j];
                        else greater = Math.min(greater, k+mat[i-1][j]);
                    }
                }
            }
            if(greater!=-1) temp.add(greater);
            set = temp;
        }
        
        int diff = 5000;
        for(int i:set){
            if(Math.abs(i-target)<diff) diff = Math.abs(i-target);
        }
        return diff;
    }
}

c++

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat[0].size();
        unordered_set<int>set({0});
        
        for(int i=0; i<m; i++){
            unordered_set<int> nextSet;
            int greater = INT_MAX;
            for(auto num:set){
                for(int j=0; j<n; j++){
                    if(num+mat[i][j]<=target) nextSet.insert(num+mat[i][j]);
                    if(num+mat[i][j]>target && num+mat[i][j]<greater) greater = num+mat[i][j];
                }
            }
            if(greater!=INT_MAX) nextSet.insert(greater);
            set = nextSet;
        }
        
        int ans = INT_MAX;
        for(auto num:set){
            if(abs(target-num)<ans) ans = abs(target-num);
        }
        return ans;
    }
};