背包问题（动态规划c++）

背包问题（动态规划c++） 背包问题（动态规划c++）

代码参考，点这里
思路参考，点这里

问题描述：

Description
卖方：这件商品14元
买方：给你20元
卖方：不好意思，我的零钱不够
买方：好吧，这是15元，剩的当小费

当到一个地方旅游时，如果你买东西的地方不支持信用，带零钱还是非常有用的。特别是有时候卖方没有零钱，如果你没有刚好的钱，你需要支付比卖价多一点。

当然你想付尽量少的钱（至少是商品价值的钱）。并且，当支付最少钱的时候，也最好是支付的硬币的数量最少。

Input
第一行包含一个整数表示测试数据的组数。每组测试数据每一行包含一个整数，表示你需要付的钱数，钱数不超过10000元。接下来包含一个整数n，表示你所拥有的钱的数量，n最多是100,接下来的n行每行一个整数，表示你有的每个硬币的面值，注意钱的面值可以是任意的，不和我们现在用的面值一样，钱的面值不超过10000元。

Output
对每组测试数据，在一行上输出两个整数：需要支付的钱数和数量。

Sample Input
1
1400
3
500
1000
2000
Sample Output
1500 2

思路:

动态规划经典二维数组m [ i ][ j ] (前i种面值的硬币可以组成价值为j的最少张数)。
m[0][0]=0。
其余全赋值为 无穷大(其实只需第一行为无穷大即可)；遇到满足条件的就加1，这样我们就求出了所有硬币组合的最少张树，当商家要1400，我们没有正好能组成1400的硬币.
有两种方法：

方法1.按列来寻找，我们从j=1400一直j++，按j列找，遍历每一行，我们找这一列里值最小的，最先找到的就是答案。

方法2 按行来寻找，每一行都要从j=1400往后遍历，找到第一个<=100的跟以前的面值和硬币个数比较，如果j小于以前满足条件的价值，肯定是当前最优，如果j等于以前满足条件的价值，我们就要比较它们的最优值m[i][j],看他对比以前最优是不是硬币个数更少。

推荐第一种方法，更快更好理解

*************图片来源

AC代码：

//参考代码 https://www.codeleading.com/article/47304952298/
//数组尽量往大了开

#include 
#include 
#include 
using namespace std;

#define mINT_MAX 2139062143 //自己定义的最大值 与下面memeset赋值相同

int m[101][30005];	//全局数组，动态规划必备二维数组，我们用全局就不用再去new一维数组赋值什么的

int main() {
    int n;	//测试数据组数
    cin >> n;

    while( n-- ) {
        memset( m, 127, sizeof( m ) );	//数组初始化，全部赋值mINT_MAX
        m[0][0] = 0;	//m[0][0]要=0，我们所有硬币个数都是根据这个来的

        int coinCount;                  //拥有硬币个数
        int coinSum = 0;                //拥有硬币值的总和
        int payMoney = 0, payCount = 0; //输出值，需要支付的硬币价值和硬币数量
        int money;                      //商家要的钱
        int value[101] = {0};	//存硬币价值

        cin >> money;
        cin >> coinCount;

        int sign = 0;	//信号sign判断输入的硬币价值有没有跟商家需求一样的，有的话就直接输出

        //输入硬币的同时计算出硬币和
        for( int i = 1; i <= coinCount; i++ ) {
            cin >> value[i];
            coinSum += value[i];	//计算硬币价值总和

            //信号sign判断输入的硬币价值有没有跟商家需求一样的，有的话就直接输出
            if( value[i] == money ) {
                sign = 1;
            }
        }

        //我们有的硬币价值跟商家需求的一样，直接输出
        if( sign == 1 ) {
            cout << money << " " << sign << endl;
        } else {
            //动态规划构建二维数组
            for( int i = 1; i <= coinCount; i++ ) {
                for( int j = 0; j <= 30000; j++ ) {		//j不能到coinSum就停，必须要大，否则会时间超限
                    if( j < value[i] ) {	//看文章递推公式
                        m[i][j] = m[i - 1][j];
                    } else {
                        m[i][j] = min( m[i - 1][j], m[i - 1][j - value[i]] + 1 );
                    }
                }
            }

            //方法1：60行-74行
            //方法1我是参考的网上代码，这个好用，是按列来寻找最优解
            int row = 0, column = 0; //把第0行第0列为初始值，存最优值的行和列

            for( int j = money; j <= 30000; j++ ) {
                for( int i = 1; i <= coinCount; i++ ) {
                    if( m[row][j] > m[i][j] ) {		//当前行比以前的都要小，这就是当前最小
                        row = i;
                        column = j;
                    }
                }

                if( row != 0 ) {	//不等于初始值，说明找到了
                    cout << column << " " << m[row][column] << endl;
                    break;
                }
            }

            //方法2 78-105行（推荐方法1，所以我注释了，）
            //方法2虽然麻烦，但是我自己写的，他是按行寻找最优解
 
        }
    }

    return 0;
}

//测试数据

第84行代码卡了我好长时间，提交一直答案错误，以为我一直没有想到j <= payMoney 的情况，我一直是小于，所以思考时一定要细心。