湊單算法——0-1背包加一層循環

題目大意：你有一張滿金額k可用得免單券，購物車裡有n個東西。設計一個算法，選出若幹件物品，使得總金額剛好大于等于k。輸出總金額即可，如果有多個結果隻用輸出任意一個

舉例：數組n:[2,3,6,9,40,96]，k=100。輸出101([2,3,96])，不用輸出具體的物品價值。

方法一：

深度搜尋，這個就不詳細講了，複雜度爆炸。

方法二：

開始沒想到~~~睡眠很重要，腦子不清醒，啥都想不到

其實對于每個物品假設它的重量和價值相同就可以了。然後從把金額k當作背包的初始可承受重量，并每次加1枚舉。

如果擷取的最大價值和目前背包可以承受的重量相同就可以跳出枚舉可承受重量的循環了。

代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int findExact(vector<int>& nums,int all_val)
{
    int len=nums.size();
    int min_num=INT_MAX;
    for(int i=all_val;;i++)    //最外層枚舉目前背包可承受重量的循環
    {
        vector<vector<int>>dp(len+1,vector<int>(i+1,0));
         for(int k=1;k<=len;k++)    //枚舉每個物品
        {
            for(int j=1;j<=i;j++)    //從1枚舉到目前背包可承受重量的循環
            {
                    if(j>=nums[k-1])dp[k][j]=max(dp[k-1][j-nums[k-1]]+nums[k-1],dp[k-1][j]);
                    else dp[k][j]=dp[k-1][j];
            }
        }
        if(dp[len][i]==i)    //如果擷取的最大價值和目前枚舉的背包可承受重量相同，就是結果
        {
            min_num=i;
            break;
        }
    }
    return min_num;

}
int main()
{
    vector<int>nums={2,3,6,9,40,96};
    int k=100;
    cout<<findExact(nums,k)<<endl;
return 0;
}