算法 递归 数据结构 c-算法问题求解，想了好久

问题描述

算法问题求解，想了好久

有一组较小的数，还有一个较大的数，求最少需要多少个较小的数的和与较大的数相等
input:
1 6 12 13 18
449
output:
27

解决方案

先将小数数组排序，然后用大数从小数中最大的数开始除，商为个数，然后再用余数和第二大的小数比较，若是大则再除，若是小则再取第三个数，以此类推

解决方案二：

感觉有点贪心算法的感觉

解决方案三：

谢谢大家了，楼主得出答案了，用的动态规划

解决方案四：

楼主可否大发慈悲把代码贴出来呢？

下面是我写的代码，希望能起到抛砖引玉的作用。能力有限，注释没写好。

#include
#include
#include

/*! Input data
/
struct InputData {
int numLtl; / Number of little numbers /
int val; /* Values of the little numbers /
int numGreat; / Value of the great number */
};
typedef struct InputData InputData;

/*! Structure for solutions
/
struct Solution {
int numLtl; / Number of little numbers /
int sumCoef; / Sum of the coefficents /
int coefs; /* Coefficients */
};
typedef struct Solution Solution;

/* brief Get the input data

  • param[in, out] pPro Pointer to input data
    /
    int getInputData(InputData     pPro)
    {
    pPro->numLtl = 5;

    pPro->val = (int*) calloc(pPro->numLtl, sizeof(int));
    if (pPro->val == NULL) {
    printf("Allocate memory failed!n");
    exit(1);
    }
    pPro->val[0] = 1;
    pPro->val[1] = 12;
    pPro->val[2] = 6;
    pPro->val[3] = 13;
    pPro->val[4] = 18;

    pPro->numGreat = 449;

    return 0;
    }

/*! breif Initialize the input data.

  • Sort the little numbers in ascending order
  • param[in, out] pro The input data
    */
    int initInputData(InputData pro)
    {
    int i, j, tmp;

    for (i=0; i
    for (j=i+1; j
    if (pro.val[i] > pro.val[j]) {
    tmp = pro.val[i];
    pro.val[i] = pro.val[j];
    pro.val[j] = tmp;
    }
    }
    }

    return 0;
    }

/* brief Display the problem

  • param[in] pro The input data
    */
    int dispPro(const InputData pro)
    {
    int i;

    printf("The little numbers: n");
    for (i=0; i<pro.numLtl; i++)
    printf("%d ", pro.val[i]);
    printf("bn");
    printf("The great number: n");
    printf("%dn", pro.numGreat);

    return 0;
    }

/*! brief Initialize the feasible solution

  • param[in,out] pSol Pointer to the feasible solution
  • param[in] numLtl Number of little numbers
    /
    int initSolution(Solution     pSol, const int numLtl)
    {
    pSol->numLtl = numLtl;
    pSol->sumCoef = 0;

    pSol->coefs = (int*) calloc(numLtl, sizeof(int));
    if (pSol->coefs==NULL) {
    printf("Allocate memory failed!n");
    exit(1);
    }
    memset(pSol->coefs, 0, numLtl*sizeof(int));

    return 0;
    }

/*! Copy solution

  • param[in] pdest Pointer to the destination
  • param[in,out] psrc Pointer to the source
    /
    int copySolution(Solution     pdest, const Solution* psrc)
    {
    pdest->sumCoef = psrc->sumCoef;
    memcpy(pdest->coefs, psrc->coefs, psrc->sumCoef*sizeof(int));

    return 0;
    }

/*! breaf Clear the solution

  • param[in,out] pSol Pointer to the solution
    /
    int clearSolution(Solution     pSol)
    {
    memset(pSol->coefs, 0, pSol->numLtl*sizeof(int));
    pSol->sumCoef = 0;

    return 0;
    }

/* brief Display the solution

  • param[in] pro Input data
  • param[in] sol Solution
    */
    int dispSol(const InputData pro, const Solution sol)
    {
    int i = 0;
    int res = pro.numGreat;

    printf("n");
    for (i=0; i
    if (sol.coefs[i] > 0) {
    printf("%d*%d + ", sol.coefs[i], pro.val[i]);
    res -= sol.coefs[i]*pro.val[i];
    }
    }
    if (res == 0)
    printf("bb= %dn", pro.numGreat);
    else
    printf("bb= %d - %dn", pro.numGreat, res);

    printf("Sum of the coefficent: %dn", sol.sumCoef);

    return 0;
    }

/* brief Count the required little numbers

  • param[in] pPro Pointer to the input data
  • param[in] pPrevSol Pointer to the previous solution
  • param[in, out] pSol Pointer to the feasible solution
  • param[in, out] ltPrev Whether the the current digits has to be
  • less than that in the previous solution
  • return The residual
    /
    int getSolution(const InputData     pPro, Solution* pSol,
    const Solution* pPrevSol, int ltPrev)
    {
    int i, j, max;
    int res = pPro->numGreat;
    InputData tmpPro;

    i = pPro->numLtl - 1;
    if (ltPrev) {
    max = pPrevSol->coefs[i] - 1;
    ltPrev = 0;
    } else
    max = pPro->numGreat / pPro->val[i];
    for (j=max; j>=0; j--) {
    pSol->sumCoef -= pSol->coefs[i];
    pSol->coefs[i] = j;
    pSol->sumCoef += j;
    if (pSol->sumCoef >= pPrevSol->sumCoef) {
    pSol->sumCoef -= pSol->coefs[i];
    pSol->coefs[i] = 0;
    break;
    }
    res = pPro->numGreat - j*pPro->val[i];
    if (res == 0)
    return 0;
    else {
    tmpPro.numLtl = pPro->numLtl-1;
    tmpPro.val = pPro->val;
    tmpPro.numGreat = res;
    if (getSolution(&tmpPro, pSol, pPrevSol, ltPrev)==0)
    return 0;
    }
    }

    return res;
    }

/* brief Get the optimal solution

  • param[in] pPro Pointer to the input data
  • param[in, out] pOptSol Pointer to the optimal solution
  • return The residual
    /
    int getOptSol(const InputData     pPro, Solution* pOptSol)
    {
    Solution tmpSol;
    int i, res;

    initSolution(&tmpSol, pPro->numLtl);
    for (i=0; inumLtl; i++) {
    tmpSol.coefs[i] = pPro->numGreat/pPro->val[i];
    tmpSol.sumCoef += tmpSol.coefs[i];
    }

    res = getSolution(pPro, pOptSol, &tmpSol, 0);
    if (res == 0) {
    do {
    copySolution(&tmpSol, pOptSol);
    clearSolution(pOptSol);
    res = getSolution(pPro, pOptSol, &tmpSol, 1);
    } while (res == 0);
    copySolution(pOptSol, &tmpSol);
    }

    return 0;
    }

/*! brief The main function
*/
int main()
{
InputData pro;
Solution sol;

getInputData(&pro);
initInputData(pro);
dispPro(pro);

initSolution(&sol, pro.numLtl);

getOptSol(&pro, &sol);

dispSol(pro, sol);

return 0;

}

解决方案五：

第一次用 CSDN，不知道怎么发代码。刚才的代码粘过来太丑了，还少了一些东西。重粘一次，如果还是很丑的话，就不敢再在 CSDN 上发东西了。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*! Input data
 */
struct InputData {
    int numLtl;     /* Number of little numbers */
    int* val;       /* Values of the little numbers */
    int numGreat;   /* Value of the great number */
};
typedef struct InputData InputData;

/*! Structure for solutions
 */
struct Solution {
    int numLtl;     /* Number of little numbers */
    int sumCoef;    /* Sum of the coefficents */
    int* coefs;     /* Coefficients */
};
typedef struct Solution Solution;

/* brief Get the input data
 * param[in, out]  pPro        Pointer to input data
 */
int getInputData(InputData* pPro)
{
    pPro->numLtl = 5;

    pPro->val = (int*) calloc(pPro->numLtl, sizeof(int));
    if (pPro->val == NULL) {
        printf("Allocate memory failed!n");
        exit(1);
    }
    pPro->val[0] = 1;
    pPro->val[1] = 12;
    pPro->val[2] = 6;
    pPro->val[3] = 13;
    pPro->val[4] = 18;

    pPro->numGreat = 449;

    return 0;
}

/*! breif Initialize the input data.
 * Sort the little numbers in ascending order
 * param[in, out]  pro     The input data
 */
int initInputData(InputData pro)
{
    int i, j, tmp;

    for (i=0; i<pro.numLtl; i++) {
        for (j=i+1; j<pro.numLtl; j++) {
            if (pro.val[i] > pro.val[j]) {
                tmp = pro.val[i];
                pro.val[i] = pro.val[j];
                pro.val[j] = tmp;
            }
        }
    }

    return 0;
}

/* brief Display the problem
 * param[in]   pro     The input data
 */
int dispPro(const InputData pro)
{
    int i;

    printf("The little numbers: n");
    for (i=0; i<pro.numLtl; i++)
        printf("%d ", pro.val[i]);
    printf("bn");
    printf("The great number: n");
    printf("%dn", pro.numGreat);

    return 0;
}

/*! brief Initialize the feasible solution
 * param[in,out]   pSol    Pointer to the feasible solution
 * param[in]   numLtl  Number of little numbers
 */
int initSolution(Solution* pSol, const int numLtl)
{
    pSol->numLtl = numLtl;
    pSol->sumCoef = 0;

    pSol->coefs = (int*) calloc(numLtl, sizeof(int));
    if (pSol->coefs==NULL) {
        printf("Allocate memory failed!n");
        exit(1);
    }
    memset(pSol->coefs, 0, numLtl*sizeof(int));

    return 0;
}

/*! Copy solution
 * param[in]   pdest   Pointer to the destination
 * param[in,out]   psrc     Pointer to the source
 */
int copySolution(Solution* pdest, const Solution* psrc)
{
    pdest->sumCoef = psrc->sumCoef;
    memcpy(pdest->coefs, psrc->coefs, psrc->sumCoef*sizeof(int));

    return 0;
}

/*! breaf Clear the solution
 * param[in,out]   pSol    Pointer to the solution
 */
int clearSolution(Solution* pSol)
{
    memset(pSol->coefs, 0, pSol->numLtl*sizeof(int));
    pSol->sumCoef = 0;

    return 0;
}

/* brief Display the solution
 * param[in]   pro     Input data
 * param[in]   sol     Solution
 */
int dispSol(const InputData pro, const Solution sol)
{
    int i = 0;
    int res = pro.numGreat;

    printf("n");
    for (i=0; i<pro.numLtl; i++) {
        if (sol.coefs[i] > 0) {
            printf("%d*%d + ", sol.coefs[i], pro.val[i]);
            res -= sol.coefs[i]*pro.val[i];
        }
    }
    if (res == 0)
        printf("bb= %dn", pro.numGreat);
    else
        printf("bb= %d - %dn", pro.numGreat, res);

    printf("Sum of the coefficent: %dn", sol.sumCoef);

    return 0;
}

/* brief Count the required little numbers
 * param[in]   pPro    Pointer to the input data
 * param[in]   pPrevSol    Pointer to the previous solution
 * param[in, out]  pSol    Pointer to the feasible solution
 * param[in, out]  ltPrev  Whether the the current digits has to be
 *      less than that in the previous solution
 * return  The residual
 */
int getSolution(const InputData* pPro, Solution* pSol,
        const Solution* pPrevSol, int ltPrev)
{
    int i, j, max;
    int res = pPro->numGreat;
    InputData tmpPro;

    i = pPro->numLtl - 1;
    if (ltPrev) {
        max = pPrevSol->coefs[i] - 1;
        ltPrev = 0;
    } else
        max = pPro->numGreat / pPro->val[i];
    for (j=max; j>=0; j--) {
        pSol->sumCoef -= pSol->coefs[i];
        pSol->coefs[i] = j;
        pSol->sumCoef += j;
        if (pSol->sumCoef >= pPrevSol->sumCoef) {
            pSol->sumCoef -= pSol->coefs[i];
            pSol->coefs[i] = 0;
            break;
        }
        res = pPro->numGreat - j*pPro->val[i];
        if (res == 0)
            return 0;
        else {
            tmpPro.numLtl = pPro->numLtl-1;
            tmpPro.val = pPro->val;
            tmpPro.numGreat = res;
            if (getSolution(&tmpPro, pSol, pPrevSol, ltPrev)==0)
                return 0;
        }
    }

    return res;
}

/* brief Get the optimal solution
 * param[in]   pPro    Pointer to the input data
 * param[in, out]  pOptSol Pointer to the optimal solution
 * return  The residual
 */
int getOptSol(const InputData* pPro, Solution* pOptSol)
{
    Solution tmpSol;
    int i, res;

    initSolution(&tmpSol, pPro->numLtl);
    for (i=0; i<pPro->numLtl; i++) {
        tmpSol.coefs[i] = pPro->numGreat/pPro->val[i];
        tmpSol.sumCoef += tmpSol.coefs[i];
    }

    res = getSolution(pPro, pOptSol, &tmpSol, 0);
    if (res == 0) {
        do {
            copySolution(&tmpSol, pOptSol);
            clearSolution(pOptSol);
            res = getSolution(pPro, pOptSol, &tmpSol, 1);
        } while (res == 0);
        copySolution(pOptSol, &tmpSol);
    }

    return 0;
}

/*! brief The main function
 */
int main()
{
    InputData pro;
    Solution sol;

    getInputData(&pro);
    initInputData(pro);
    dispPro(pro);

    initSolution(&sol, pro.numLtl);

    getOptSol(&pro, &sol);

    dispSol(pro, sol);

    return 0;
}

[/code]```

解决方案六：

#include
#include "csce310a04part02.h"
#include
#include
#include

using namespace std;
int fewestPlates( vector plateWeight , int objectWeight ){
vector numbers;
numbers.push_back(0);
for(int i=0;i<plateWeight.size();i++){
numbers.push_back(plateWeight[i]);
}
int state[objectWeight+1][numbers.size()];
for(int i=0;i<objectWeight+1;i++){
state[i][0]=10000;
}
state[0][0]=0;
for(int i=1;i<numbers.size();i++){
for(int j=0;j<objectWeight+1;j++){
if(j<numbers[i]){
state[j][i]=state[j][i-1];
}else{
state[j][i]=min(state[j][i-1],state[j-numbers[i]][i]+1);
}
}
}
return state[objectWeight][numbers.size()-1];
}

时间： 2024-04-24 00:54:24

算法 递归 数据结构 c-算法问题求解，想了好久的相关文章

字符串搜索-Boyer-Moore算法 《数据结构与算法c++版》Adam Drozdek

问题描述 Boyer-Moore算法 <数据结构与算法c++版>Adam Drozdek 通常BM算法采用的是坏字符和好后缀算法(eg.,BM算法),我学习的<数据结构与算法c++版>Adam Drozdek版教材上使用了 全后缀和部分后缀规则,这种方法在网络上基本查不到. 作者解释原理时,一个关键的函数只是给出公式,基本上没有解释,如下: 请问怎么理解这个公式,尤其是公式中的s代表什么意思? 原书我已经在云盘共享,关于BM算法书上在P687面.希望能帮忙解决.

算法 递归 数据结构-算法数据结构关于查找比较的小问题。通过“比较”找n个整数中最大

问题描述 算法数据结构关于查找比较的小问题.通过"比较"找n个整数中最大 通过"比较"找n个整数中最大数时,算法至少要做＿次. A.log n B.nlog n C.n-1 D.n 解决方案 答案应该是C.每个值比较一次即可.

算法 递归 数据结构-求解释代码，添加注释或者画图解释（在网上看到的求组合的递归算法，绕晕头了看不懂，求解释）

问题描述 求解释代码,添加注释或者画图解释(在网上看到的求组合的递归算法,绕晕头了看不懂,求解释) public class Test1 { public static void main(String[] args) { select(2); } private static void select(int k) { char[] result = new char[k]; subselect(0 1 result k); } private static void subselect(int

算法 递归 数据结构-2个1中间有1个数，2个n之间有n个数

问题描述 2个1中间有1个数,2个n之间有n个数 一组数1 1 2 2 3 3 4 4.....n n,经过操作后输出 使得 两个1之间有1个数 两个2之间有2个数 两点n之间有n个数 可以有0 对于确定n输出所有可能情况 解决方案 2N个数排成一行(每个数有2个), 2个1之间有1个数,2个2 之间有2个数,...2个N之间有N个数... 例312132 解决方案二: nXn方Xn3次方...Xn的n次方得到结果? 解决方案三: 如果是0的话那就是(n+1)的2分之(n + n 方)次方 解决

数据结构与算法系列（2）基础排序算法

前言 在计算机中实现存储数据最普遍的两种操作就是排序和查找.这是从计算机产业初始就已经确认的 了.这意味着排序和查找也是计算机科学领域最值得研究的两种操作.本书提到的许 多数据结构的主要设计目的就是为了使排序和/或查找更加简单,同时也是为了数据在结构内的存 储更加有效. 本章会介绍有关数据排序和查找的基础算法.这些算法仅依赖数组作为数据结构,而且所采用的 "高级"编程技术只是递归.本章还介绍了用来非正式分析不同算法之间速度与效率的方 法,此方法贯穿全书. 1.排序算法 人们在日常生活中

数据结构经典算法

C#选择排序 using System:namespace SelectionSorter{ public class SelectionSorter{ private int min:public void Sort(int [] list){ for(int i=0:i<list.Length-1:i++){ min=i:for(int j=i+1:j<list.Length:j++){ if(list[j]<list[min])min=j:}int t=list[min]:list

《数据结构与算法：Python语言描述》一1.2　问题求解：交叉路口的红绿灯安排

1.2 问题求解:交叉路口的红绿灯安排 本节展示一个具体问题的计算机求解过程,以此说明在这种过程中可能出现的一些情况,需要考虑的一些问题,以及一些可能的处理方法. 交叉路口是现代城市路网中最重要的组成部分,繁忙的交叉路口需要用红绿灯指挥车辆通行与等待,正确的红绿灯调度安排对于保证交通安全.道路运行秩序和效率都非常重要.交叉路口的情况多种多样,常见形式有三岔路口.十字路口,也有较为少见的更复杂形式的路口.进一步说,有些道路是单行线,在中国的交叉路口还有人车分流和专门的人行/自行车红绿灯等许多情况,

《数据结构与算法 C语言版》—— 3.3栈与递归实现

3.3栈与递归实现 3.3.1递归的定义 栈还有一个重要应用是在程序设计语言中实现递归.一个直接调用自己或通过一系列的调用语句间接调用自己的函数,称为递归函数.其中直接调用自己的函数称为直接递归.间接调用自己的函数称为间接递归. 递归是算法设计中最重要的手段.它通常把一个大型的复杂问题转化为一个与原问题相似的规模较小的问题来求解.下面是常见的使用递归的三种情况. (1)定义是递归的 现实中,有许多定义是递归定义的,以n!为例来说明,其定义如下: fact(n)=1n=0//递归终止条件 n*fa

递归算法-数据结构 算法 递归

问题描述 数据结构 算法 递归 编写一个递归算法,删除二叉树中所有叶子结点. 解决方案 void foo(Node * node) { if (node->left != null) { if (node->left->left == null && node->left->right == null) { delete(node->left); node->left = null; } else { foo(node->left); } }