藍橋杯 動态規劃+背包

公司發了某商店的購物券1000元，限定隻能購買店中的m種商品。每種商品的價格分别為m1,m2,…，要求程式列出所有的正好能消費完該購物券的不同購物方法。

程式輸入：

第一行是一個整數m，代表可購買的商品的種類數。

接下來是m個整數，每個1行，分别代表這m種商品的單價。

程式輸出：

第一行是一個整數，表示共有多少種方案

第二行開始，每種方案占1行，表示對每種商品購買的數量，中間用空格分隔。

例如：

輸入：

2

200

300

則應輸出：

2

2  2

5  0

輸入：

2

500

800

則應輸出：

1

2  0

要求考生把所有函數寫在一個檔案中。調試好後，存入與考生檔案夾下對應題号的“解答.txt”中即可。相關的工程檔案不要拷入。 

#include <cstdio>   
#include <cstdlib> 
#include <list>
#include <string>
#include <iterator>
#include <iostream>
using namespace std;

int *a,*b;       
int n;   
int count = 0;   

list<string> meanprintf;

void print()   
{   
    int i;
	string temp("");
	char cc;
	for(i = 0; i < n; i++){   
        cc=b[i]+'0';
		temp+=cc;
		if(i!=n-1)
			temp+=' ';
		}
	meanprintf.push_back(temp);
}   
void problem9(int total,int size)   
{   
    if(size != n )   
    {   
        if(total == 0)//判斷背包是否正裝滿   
        {   
            count++;//存放可行方案的個數   
            print();//輸出此可行解   
        }   
        else  
        {   
            problem9(total,size + 1);//未放入物品a【size】的情況   
            if(total - a[size] >= 0)//判斷放入a【size】後，是否會超出背包的承載   
            {   
                b[size]++;//使得a【size】對應物品的數量加1   
                problem9(total - a[size],size);//放入物品a[size]的情況   
                b[size]--;//使得相應的物品數量減1   
            }   
        }   
    }   
  
}   
void main()   
{   
    int i,j;   
    scanf("%d",&n);   
    a = (int*)malloc(sizeof(int) * n);   
    b = (int*)malloc(sizeof(int) * n);   
    for(i = 0; i < n; i++)   
        scanf("%d",&a[i]);   
    for(j = 0; j < n; j++)   
        b[j] = 0;   
    problem9(1000,0);   
    printf("%d\n",count);   
	for (list<string>::iterator iter=meanprintf.begin();iter!=meanprintf.end();++iter)
		cout<<*iter<<endl;
}