有一组较小的数，还有一个较大的数，求最少需要多少个较小的数的和与较大的数相等
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.
\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("\b\n");
printf("The great number: \n");
printf("%d\n", pro.numGreat);
return 0;
}
/*! \brief Initialize 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,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] 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("\b\b= %d\n", pro.numGreat);
else
printf("\b\b= %d - %d\n", pro.numGreat, res);
printf("Sum of the coefficent: %d\n", sol.sumCoef);
return 0;
}
/* \brief Count the required little numbers
\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
\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("\b\n");
printf("The great number: \n");
printf("%d\n", 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("\b\b= %d\n", pro.numGreat);
else
printf("\b\b= %d - %d\n", pro.numGreat, res);
printf("Sum of the coefficent: %d\n", 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];
}