[凑硬币问题]
这是一个背包问题，但是我要的不是这些，第一个给出背包代码的，20分。其他的不给分。
给出我要的结果的，又分。
我要什么结果呢？先看题目。
你有（足够的）5分，2分，1分的硬币，现在要凑出来12分的结果，那么最少的硬币组合是？
结果肯定是 【5 5 2】
那么给你的硬币是 5分的，4分的(虽然我没有见过)，1分的，凑8分，怎么凑？
贪婪算法可能给出 【5 1 1 1】，但是显然应该是【4 4】
我现在要的代码 不是那10行背包代码。
而是要能输出需要哪些硬币的结果，比如对于5，4，1凑8这个，你要输出4，4。
我不关注是2枚硬币，还是3枚。
[解决办法]
#include <iostream>#include <vector>#include <string>using namespace std;void getResult(vector<int> var, vector<int> &res, int total){ int totalNum = 0; //需要的硬币总数 int minNum = 9999; //最小的硬币总数 vector<int>::iterator iter = var.begin(); vector<int>::iterator ivec = iter; while(ivec != var.end()) { int tmp = total; while(iter != var.end()) { int num = tmp / (*iter); totalNum += num; tmp = tmp - num * (*iter++); } if(tmp != 0) { totalNum = 0; ++ivec; iter = var.begin(); continue; } if(totalNum < minNum) { int t = total; minNum = totalNum; res.clear(); res.resize(ivec - var.begin(), 0); for(vector<int>::iterator itemp = ivec; itemp != var.end(); ++itemp) { int num = t / (*itemp); res.push_back(num); t = t - num * (*itemp); } } totalNum = 0; ++ivec; iter = ivec; }}bool checkLegal(vector<int> var, vector<int> res, int total){ int result = 0; for(vector<int>::size_type i = 0; i < var.size(); ++i) { result = result + (var[i] * res[i]); } return (result == total);}int main(){ vector<int> ivar, iresult; //ivar用来存贮硬币种类，iresult用来存贮硬币数量 int total, var; cout<<"请输入你需要计算的结果: "<<endl; cin>>total; cout<<"硬币种类:"<<endl; while(cin>>var) ivar.push_back(var); //此处略过排序，假设硬币是从大到小输入 iresult.resize(ivar.size(), 0); getResult(ivar, iresult, total); if(checkLegal(ivar, iresult, total)) { for(vector<int>::size_type i = 0; i < ivar.size(); ++i) { cout<<"硬币"<<ivar[i]<<"需要"<<iresult[i]<<"枚"<<endl; } } else { cout<<"分配失败"<<endl; } return 0;}
[解决办法]
#include <iostream>#include <vector>using namespace std;void InsertSort(vector<int>& _data)//unfinished{}vector<int> corns;bool GenerateSolution(int r, size_t i, vector<int>& res){ size_t resSize = res.size(); size_t cornSize = corns.size(); if(r == 0) return true; else if(i >= cornSize) return false; if(r - corns[i] >= 0) { res. push_back(corns[i]); if(GenerateSolution(r-corns[i], i, res)) { if(cornSize > i+1 && corns[i+1] * (res.size() -resSize) > r) { vector<int> nextRes; if(GenerateSolution(r, i+1, nextRes)) { int popSize = res.size()-resSize; if(nextRes.size() < popSize) { for(int j=0; j<popSize; ++j) res.pop_back(); for(int j=0; j<nextRes.size(); j++) res.push_back(nextRes[j]); } } } return true; } else { return GenerateSolution(r, i+1, res); } } else { return GenerateSolution(r, i+1, res); }}int main(){ int input = 1; cout<<"Please input corns: (End with number <=0)"<<endl; while(input > 0) { cin>>input; if(input > 0) { corns.push_back(input); } } InsertSort(corns); vector<int> res; do { cout<<"Please input number to charge: "<<endl; cin>>input; if(input < 1) { break; } res.clear(); if(GenerateSolution(input, 0, res)) { cout<< res.size()<<":\t"; for(int i=0; i<res.size(); ++i) { cout<<res[i]<<"\t"; } cout<<endl; } else{ cout<<"Not Found Solution!"<<endl; } }while(true); return 0;}
[解决办法]
依然背包
void solve(int* a,int n,int m) { int b[100] = { 0 }; vector<int> v[100]; for(int i = 0 ; i < n ; ++ i) { b[a[i]] = 1; v[a[i]].push_back(a[i]); } for(int i = 1 ; i <= 100 ; ++ i) { if(b[i]) continue; for(int j = 1 ; j <= i ; ++ j) { if(b[i] == 0 || b[i]> b[j] + b[i - j]) { b[i] = b[j] + b[i - j]; v[i] = v[j]; copy(v[i - j].begin(),v[i - j].end(),back_inserter(v[i])); } } } cout<<"min count is : "<<b[m]<<" \ngroup by : "; copy(v[m].begin(),v[m].end(),ostream_iterator<int>(cout," ")); cout<<endl; } void main() { int a[] = {5,2,1}; vector<int> v; solve(a,3,12); }
[解决办法]
大家看看有没有什么问题，为什么我觉得挺简单的呀，是不是我理解错了题意？
#include <stdio.h>#include <stdlib.h>void foo(int n, int a[], int len)//n为硬币的总和，a中存储硬币的可选面值，len为可选硬币的种类（即a的长度）{ int i; int *b = (int*)malloc(sizeof(int)*n); bool flag = true; for(i=0; i<n && flag; ++i) { int j; for(j=0; j<=i; ++j) { b[j] = 0; } while(b[0]<len) { int sum = 0; for(j=0; j<=i; ++j) { sum += a[b[j]]; } if(sum==n) { flag = false; for(j=0; j<=i; ++j) { printf("%d ", a[b[j]]); } printf("\n"); } { ++b[i]; for(j=i; j>0 && b[j]==len; --j) { ++b[j-1]; } int k; int temp = b[j]; for(k=j+1; k<=i; ++k) { b[k] = temp; } } } } }void main(){ int a[3] = {5, 4, 1}; foo(8, a, 3);//8为硬币的总和，a中存储硬币的可选面值（5，4，1），len为可选硬币的种类（即a的长度，3种）}
[解决办法]
public static int getResult(int step1,int step2,int step3,int sum){ int temp = 0; int flag = 0; for(int i=0;i<sum/step1;i++){ for(int j=0;j<sum/step2;j++){ for(int k=0;k<sum/step3;k++){ temp = step1*i + step2*j + step3*k; if(temp == sum){ flag++; System.out.println(i + "*1 " + j + "*2 " + k + "*4 "); } } } } System.out.println(flag); return flag; }
[解决办法]
using System;using System.Collections.Generic;using System.Text;namespace ConsoleApplication1{ class Program { private static readonly List<int> _storage = new List<int> { 5, 2, 1 }; private static int number; private static List<int> result = new List<int>(); static void Main(string[] args) { Console.WriteLine("Plesse input a number."); number = int.Parse(Console.ReadLine()); while (number > 0) { foreach (var i in _storage) { while (Subtractor(i)) { } } } var sb = new StringBuilder(); foreach (var s in result) { sb.Append(s.ToString() + ','); } Console.WriteLine(sb.ToString()); Console.ReadLine(); } private static bool Subtractor(int toSubtracting) { if (number < toSubtracting) { return false; } if (number >= toSubtracting) { result.Add(toSubtracting); number -= toSubtracting; return true; } return false; } }}
[解决办法]
bool tick_coins(int sum, const int* coins, int* coinCount, int c){ int r = sum; //运输余额 for (int i=1; r; i++) //硬币个数 { memset(coinCount, 0, c*sizeof(int)); r = sum - (coinCount[0] = i) * coins[0]; if (r > 0) continue; //全用最大硬币还有余额, 硬币数不够 int j = 1, n = 0; while (r) { if (j == c) { //全部用最小的硬币, i个硬币到此已经无法拼出总额了. break; } if ((n == 0) || (r < 0)) { r += coinCount[j] * coins[j]; n += coinCount[j]; coinCount[j--] = 0; while ((j >=0) && (coinCount[j] == 0)) j--; if (j == -1) break; r += coins[j]; coinCount[j++]--; n++; } else { const int v = coins[j]; while ((n > 0) && (r >= v)) { r -= v; coinCount[j]++; n--; } if ((n > 0) && (r > 0)) ++j; } } } return (r == 0);}int _tmain(int argc, _TCHAR* argv[]){ int coin[3] = {5, 4, 1}; int coinCount[3] = {0}; for (int i=1; i<50; i++) { tick_coins(i, coin, coinCount, 3); } return 0;}