首页 > 试题广场 >

Find More Coins (30)

[编程题]Find More Coins (30)
  • 热度指数：2342 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

输入描述:
Each input file contains one test case.  For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay).  The second line contains N face values of the coins, which are all positive numbers.  All the numbers in a line are separated by a space.


输出描述:
For each test case, print in one line the face values V1 <= V2 <= ... <= Vk such that V1 + V2 + ... + Vk = M.  All the numbers must be separated by a space, and there must be no extra space at the end of the line.  If such a solution is not unique, output the smallest sequence.  If there is no solution, output "No Solution" instead.
Note: sequence {A[1], A[2], ...} is said to be "smaller" than sequence  {B[1], B[2], ...} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].
示例1

输入

8 9
5 9 8 7 2 3 4 1

输出

1 3 5
算法知识视频讲解
添加回答
Hewitt头像 Hewitt 



优雅解决




#include <bits/stdc++.h>
using namespace std;
int a[10100],b[110];
vector<int> dp[110];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    dp[0].push_back(0);
    for(int i=n-1;i>=0;i--){   //倒序保证字典需最小
        for(int j=m;j>=a[i];j--){
            if(dp[j-a[i]].size()!=0){dp[j]=dp[j-a[i]];dp[j].push_back(a[i]);}
        }
    }
    if(dp[m].size()==0)printf("No Solution\n");
    else{
        for(int i=dp[m].size()-1;i>=1;i--)printf("%d ",dp[m][i]);
    }
    return0;
}

编辑于 2020-07-21 18:06:32 回复(1)
C/C++
Dave_lzw头像 Dave_lzw 
/*注意到只有100，直接dfs，当然也可以按照装满背包做*/
#include <bits/stdc++.h>
using namespace std;
int n , k , x , f ;
vector<int>res,tmp;
map<int,int>mp;
void dfs( int m ) {
	if( f ) return ; 
	if( !m ) { f = 1 ; res = tmp ; return ; }
	for( auto i : mp ) {
		if( i.second ) {
			if( m >= i.first ) {
				mp[i.first] --; 
				tmp.push_back(i.first);
				dfs( m - i.first );
				tmp.pop_back();
				mp[i.first] ++; 
			}
		}
	}
}
int main() {
	scanf("%d%d",&n,&k);
	for( int i = 0 ; i < n ; i++ ) {
		scanf("%d",&x);
		if( x <= k ) mp[x] ++ ;
	}
	f = 0 ;
	dfs(k);
	if( !res.size() ) return 0*printf("No Solution");
	int len = res.size();
	for( int i = 0 ; i < len ; i++ ){
		printf("%d",res[i]);
		if( i != len - 1 ) printf(" ");
	}
	return 0 ;
}

编辑于 2020-02-27 20:29:00 回复(0)
Myhui头像 Myhui 
//题目解析来自@cheerss https://www.jianshu.com/p/20dac38241a5 //这是一道01背包问题，解题时注意题意的转化：可以将每个coin都看成value和weight都相同的物品
//1. 要求所付的钱刚刚好，相当于要求背包必须刚好塞满，且价值最大。
// （限制背包体积相当于限制coin的总和不能超过所要付的钱，在此条件下求coin组合的最大值，
//   如果这个最大值刚好等于要付的钱，则有解，此时背包也刚好处于塞满状态，否则无解）
//2. 最后要求从小到大输出coin的组合，且有多解时输出最小的组合。
//   我们应该将coin从大到小排序，在放进背包时也从大到小逐个检查物品，更新背包价值的条件是在加入一个新的物品后，价值>=原价值，
//   由于物品是从大到小排序的，如果一个新的物品的加入可以保证价值和原来相同，则此时一定是发现了更小的组合。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=10010;
const int maxv=110;
int w[maxn],dp[maxv]={0};                        //w[]为钱币的价值
bool choice[maxn][maxv];                         //choice[i][j]表示计算dp[i][j]时是否选择了i物品
vector<int> ans;
bool cmp(int a,int b){
    return a>b;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    sort(w+1,w+n+1,cmp);                          //从大到小排序（以求得字典序最小的情况）
    for(int i=1;i<=n;i++){                        //逆序遍历（dp[i][j]只与dp[i-1][j]和dp[i-1][j-w[i]]有关，即只和i-1时刻状态有关）；下边界w[i]，因为j<w[i]使得j-w[i]为负数无意义
        for(int j=m;j>=w[i];j--){                 //如果正序遍历则当求dp[v]时其前面的dp[0],dp[1]，…，dp[j-1]都已经改变过，里面存的都不是i-1时刻的值，这样求dp[j]时利用dp[j-w[i]]必定是错的值。
            if(dp[j]<=dp[j-w[i]]+w[i]){           //等于号也要取（如果一个新的物品的加入可以保证价值和原来相同，则此时一定是发现了更小的组合。）          
                dp[j]=dp[j-w[i]]+w[i];
                choice[i][j]=true;                //放入第i件物品
            }
            else choice[i][j]=false;
        }
    }
    if(dp[m]!=m) cout<<"No Solution";             //无解（本题容量与价值合二为一），刚好塞满背包容量即等于最大价值
    else{
        int v=m,index=n;
        while(v>0){                               //从后往前寻找输出路径（得到之前修改dp[]时的选择物品情况），从后往前是因为物品价值从大到小排列，而输出要从小到大
            if(choice[index][v]==true){
                ans.push_back(w[index]);
                v-=w[index];
            }
            index--;
        }
        for(int i=0;i<ans.size();i++){
            if(i!=0) cout<<" ";
            cout<<ans[i];
        }
    }
    return 0;
}

发表于 2019-02-21 17:59:09 回复(2)
刘涛201801031713506头像 刘涛201801031713506
这个题目可以用dfs或者动态规划去做，但是dfs会超时和超过内存（为了拿点分的可以用这个，思路简单）再次提醒自己#include<string.h>不能遗漏了，否则会报编译错误

#include<stdio.h>

#include<iostream>

#include<string>

#include<string.h>

#include<vector>

#include<algorithm>

using namespace std;


int mark[10010];

vector<int> finalresult;

void dfs2(vector<int> input,int index,int sum,int M)

{

    if(sum>M||index>input.size()-1||input[index]>M)

        return;

    if(sum==M&&finalresult.size()==0)

    {

        for(int i=0;i<input.size();i++)

        {

            if(mark[i]>0)

                finalresult.push_back(input[i]);

        }

        return;

    }

    mark[index]++;

    dfs2(input,index+1,sum+input[index],M);

    mark[index]--;

    dfs2(input,index+1,sum,M);

}


int main()

{

    memset(mark,0,sizeof(mark));

    vector<int> input;

    int N,M;

    scanf("%d %d",&N,&M);

    for(int i=0;i<N;i++)

    {

        int tmp;

        scanf("%d",&tmp);

        input.push_back(tmp);

    }

    sort(input.begin(),input.end());


    if(input.size()==1&&M==input[0])

    {

        cout<<M<<endl;

        return 0;

    }

    dfs2(input,0,0,M);


    if(finalresult.size()==0)

        cout<<"No Solution";

    else

    {

        for(int i=0;i<finalresult.size();i++)

        {

            cout<<finalresult[i];

            if(i!=finalresult.size()-1)

            {

                cout<<" ";

            }

        }

    }

    cout<<endl;

    return 0;

}


发表于 2018-03-15 21:32:51 回复(2)
C/C++
nbgao头像 nbgao 
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 10010;
const int MAXV = 103;
int w[MAXN],dp[MAXV]={0};
bool choice[MAXN][MAXV],flag[MAXN];

bool cmp(int a, int b)
{     return a>b;
}

int main()
{     int n,m;     cin>>n>>m;     for(int i=1;i<=n;i++)         cin>>w[i];     sort(w+1,w+n+1,cmp);     for(int i=1;i<=n;i++)     {         for(int j=m;j>=w[i];j--)         {             if(dp[j] <= dp[j-w[i]] + w[i])             {                 dp[j] = dp[j-w[i]] + w[i];                 choice[i][j] = true;             }else                 choice[i][j] = false;         }     }     if(dp[m] != m)         cout<<"No Solution\n";     else{         int k=n,num=0,v=m;         while(k>=0)         {             if(choice[k][v] == true)             {                 flag[k] = true;                 v -= w[k];                 num++;             }else                 flag[k] = false;             k--;         }         for(int i=n;i>=1;i--)         {             if(flag[i] == true)             {                 cout<<w[i];                 num--;                 if(num>0)                     cout<<" ";             }         }         cout<<endl;     }     return 0;
}

发表于 2018-03-03 00:39:23 回复(0)
老石基头像 老石基 
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int[] coins = new int[n];
		for(int i = 0;i<n;i++)
			coins[i] = in.nextInt();
		Arrays.sort(coins);
		int[] result = new int[n];
		int j = find(coins, 0, result, 0, m);
		if(j<0){
			System.out.println("No Solution");
		}else{
			for(int i = 0;i<j;i++)
				System.out.print(result[i]+" ");
			System.out.println(result[j]);
		}
	}
	
	private static int find(int[] coins,int start,int[] result,int j,int m){
		for(int i = start;i<coins.length;i++){
			if(coins[i]<m){
				//当前位置符合 找下一个位置
				result[j] = coins[i];
				int flag = find(coins, i+1, result, j+1, m-coins[i]);
				if(flag!=j)
					return flag;
				result[j] = 0;
			}else if(coins[i]==m){
				result[j] = coins[i];
				return j;
			}else
				return j-1;
		}
		return j-1;
	}
}

发表于 2016-07-25 16:31:37 回复(0)
gyr679头像 gyr679
01背包问题，要输出字典序最小的方案，要将硬币值从大到小排序，当选择当前硬币可以满足要求时要更新方案。dp[i]表示能否表示出i，G[i]表示表示出i最小的方案序列。 
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

const int N = 1e4 + 5;
const int M = 105;

int n, m;
int coins[N];
bool dp[M];
vector<int> G[M];

bool cmp(int x, int y) { return y < x; }

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> coins[i];
  sort(coins + 1, coins + n + 1, cmp);
  dp[0] = true;
  for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 0; j--) {
      if (j >= coins[i]) {
        dp[j] |= dp[j - coins[i]];
        if (dp[j - coins[i]]) {
          G[j].clear();
          for (int val : G[j - coins[i]]) G[j].push_back(val);
          G[j].push_back(coins[i]);
        }
      }
    }
  }
  if (dp[m]) {
    reverse(G[m].begin(), G[m].end());
    for (int val : G[m]) cout << val << ' ';
  } else
    puts("No Solution");
  return 0;
}


发表于 2022-08-23 16:06:24 回复(0)
羽落无痕123头像 羽落无痕123
题目要求选择的物品价值总和恰为m，因此在背包问题中将容量V设为m，最终判断dp[n][m]：n件物品，容量上限为m时，最大价值是否为m。同时，将物品价值从大到小排列，意在出现dp[i][j]==d[i-1][j-value[i]]时，优先选择价值量小的物品。最后，从choice[n][m]开始输出选择的物品价值。 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+1;
int n,m,value[maxn],dp[101];
bool choice[maxn][101];

//dp[i][j]:前i件物品容量为j时的最大价值
//本题重量=价值，最终判断dp[n][m]==m即可，固定容量为m，前n件物品的最大价值是否达到m
void DP(){
    sort(value+1,value+n+1,greater<int>());
    //背包问题初始化 dp[0][j]=0
    for(int i=1;i<=n;i++){
        //1维dp，倒着枚举容量
        for(int j=m;j>=value[i];j--){
            if(dp[j-value[i]]+value[i]>=dp[j]){
                dp[j]=dp[j-value[i]]+value[i];
                choice[i][j]=true;
            }else{
                choice[i][j]=false;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>value[i];
    DP();
    if(dp[m]!=m){
        cout<<"No Solution";
        return 0;
    }
    int k=n,v=m;//物品编号，容量
    while(v!=0){
        if(choice[k][v]){
            cout<<value[k];
            v-=value[k];
            if(v!=0) cout<<" ";
        }
        k--;
    }
    return 0;
}


编辑于 2022-08-13 16:50:56 回复(0)
有糖吗头像 有糖吗
因为最大要付100元，所以需要计算的硬币最大值也是一百元，直接用数组记录就好啦。 
#include<cstdio>
int a[101] = { 0 }, b[101] = { 0 };
int n, m, z;
bool dfs(int i, int amo) {
	while (a[i] == 0 && i < 101) i++;
	if (i > 100) return false;
	for (int j = a[i]; j >= 0; j--) {
		if (amo == i*j) {
			z = i;
			b[i] = j;
			return true;
		}
		else if (amo > i*j) {
			if (dfs(i + 1, amo - i*j)) {
				b[i] = j;
				return true;
			}
		}
	}
	return false;
}
int main() {
	int t;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", &t);
		if (t < 101) a[t]++;
	}
	if (dfs(1, m)) {
		for (int i = 1; i < z; i++) {
			if (b[i]) {
				while (b[i]--) {
					printf("%d ", i);
				}
			}
		}
		while (--b[z]) printf("%d ", z);
		printf("%d", z);
	}
	else printf("No Solution");
	return 0;
}


发表于 2020-04-03 21:50:22 回复(0)
默默丶头像 默默丶
//dfs,从小到大排序，找到的第一个解一定是最优的
//向量赋值可以直接用=，改变前者，不会影响后者，不是副本。 
#include<iostream>
(720)#include<vector>
#include<algorithm> //1 2 3 4 5 7 8 9 
using namespace std;
int N, M,x;
vector<int>coins(N);
bool dfs(vector<int>vec, int i) {
	int sum = 0;
	for (int k = 0; k < vec.size(); k++) {
		sum += vec[k];
	}
	if (sum == M) {//第一次就是最小的
		for (int k = 0; k < vec.size(); k++) {
			if (k) printf(" ");
			printf("%d", vec[k]);
		}
		return true;
	}
	else if (sum < M) {
		for (int j = i; j < N; j++) {
			vector<int>tmp;
			/*for (int k = 0; k < vec.size(); k++) {
				tmp.push_back(vec[k]);
			}*/
			tmp = vec;
			tmp.push_back(coins[j]);
			bool flag=dfs(tmp, j + 1);
			if (flag) { return true; }
		}
	}
	return false;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >>x;      
		coins.push_back(x);
	}
	sort(coins.begin(), coins.end());
	vector<int>ans;
	bool ff=dfs(ans, 0);
	if (!ff) { printf("No Solution"); }
}


发表于 2020-03-19 10:48:55 回复(0)
Python
初心者托奇头像 初心者托奇
牛客勉强全过，pta上差一个，先这样吧 
a = list(map(int,input().split(' ')))
b = sorted(list(map(int,input().split(' '))),reverse = True)
i = 0;q = a[1];p = 0;c = '';e = ''

while i < len(b):
    if b[i] == q:
        c = e + chr(b[i] + 48);f = 1;i += 1
    elif b[i] < q:
        j = a[0] - 1 - p
        while i - j:
            if b[i] + b[j] < q:j -= 1           # 一级副光标
            elif b[i] + b[j] > q:i += 1         # 一级主光标
            else:break
        else:break
        
        m = a[0] - 1 - p;n = j;r = b[j]
        while m - n > 0:
            if b[m] + b[n] < r:m -= 1           # 二级副光标
            elif b[m] + b[n] > r:n += 1         # 二级主光标
            else:
                e += chr(b[m] + 48);b.remove(b[m])
                p += 1;r = b[n];m = a[0] - 1 - p;n += 1;continue
        else:e += chr(r + 48);b.remove(r);p += 1;q = b[i]

    else:i += 1

if c:
    c = list(map(lambda x:x - 48,map(ord,sorted(c))));i = 0
    while i < len(c) - 1:
        if c[i] > b[-1]:
            for j in range(-2,-len(b),-1):
                if c[i] + c[-1] == b[-1] + b[j]:
                    c.append(b[-1]);c.append(b[j]);del b[-1];del b[j]
                    b.append(c[-1]);b.append(c[i]);del c[-3];del c[i]
                    b = sorted(b,reverse = True);c = sorted(c);break
        i += 1
    print(' '.join(map(str,c)))
else:
    print('No Solution')

发表于 2020-02-03 14:35:13 回复(0)
牛客118466954号头像 牛客118466954号
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int N,M;
int coin[10004];
int mark[10004];
int find_answer;
void search(int value,int from){
    for(int i=from;i<N;i++){
        if(value-coin[i]==0){
            find_answer=1;
            mark[i]=1;
            return;
        }
        else if(value-coin[i]<0){
            find_answer=0;
        }else{
            mark[i]=1;
            search(value-coin[i],i+1);
        }
        
        
        if(!find_answer) mark[i]=0;
        else
            break;
    }
    return;
}
int main(){
    memset(coin,0,sizeof(coin));
    memset(mark,0,sizeof(mark));
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        scanf("%d",&coin[i]);
     sort(coin,coin+N);
     for(int i=0;i<N;i++){
         if(M-coin[i]==0){
             mark[i]=1;
             find_answer=1;
             break;
         }
         else if(M-coin[i]<0){
             find_answer=0;
             break;
         }else
             search(M,i);
         
             
                  
         if(find_answer)
             break;
     }
     
     
     
     if(!find_answer)
         printf("No Solution");
    else {
        for(int i=0;i<N;i++)
            if(mark[i])
                if(i==N-1)
                    printf("%d",coin[i]);
                else
                    printf("%d ",coin[i]);
    }
     
} 
发表于 2020-01-18 14:31:17 回复(0)
C/C++
BlackCarDriver头像 BlackCarDriver
//用递归解决
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10009;
int eoa = 0;//the end of the array
int coin[maxn]; //the value of each coin
vector<int>ans;    //save the ans_coin

int recusion(int index, int need){
    if (index >= eoa)return -1; //cant not find an answer
    int now = coin[index];
    if (now > need) return -1;    //cant not find the answer by it way
    if (need == now){    //finally find the last used coin
        ans.push_back(now);
        return need;
    }
    int res = recusion(index + 1, need - now); //take this coin
    if (res != -1){
        ans.push_back(now);
        return res;
    }
    return recusion(index + 1, need);    //dont take it coin
}
int main(){
    int m;    
    cin >> eoa >> m;
    for (int i = 0; i < eoa; i++){
        cin >> coin[i];
    }
    sort(coin, coin + eoa);
    int res = recusion(0, m);
    if (res != -1){
        for (int i = ans.size()-1; i>0; i--){
            cout << ans[i] << " ";
        }
        cout << ans[0]<< endl;
    }
    else cout << "No Solution" << endl;
}
发表于 2019-03-28 12:29:52 回复(0)
成为offer收割机1头像 成为offer收割机1

8 9
5 9 8 7 2 3 4 1
true true true true true true true true true true 
true false true true true true true true true true 
true false false true true true false true true true 
true false false false true true false true true true 
true false false false false true false true true true 
true false false false false false false true true true 
true false false false false false false false true true 
true false false false false false false false false true 
1 3 5
我们用bool数组can[x][y]表示用[x..n - 1]的硬币是否能凑出y块钱， 
初值全是false，只有can[n][0] = true， 因为这表示什么硬币都不用，我们只能凑出0块钱。 
递推： 
can[i][j] = can[i + 1][j] || can[i + 1][j - a[i]];
这表示要用[i..n - 1]的硬币凑出j块钱，要么就是用[i + 1.. n - 1]已经凑好了，这样不需要第i个硬币。 
要么用第i个硬币，并用[i + 1..n - 1]个硬币凑出j - a[i]块钱。
例如9在【9】【9】是true因为之前已经凑出0元加上9是9为真
例如【1】【6】由于前0-5已经凑出【2】【4】已经凑出来了所以加上2正好为真
反过来，用第i个硬币相减相应的值然后就可以看是否为真

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**

  • @author 孙荣达
    */
    public class Main {

    public static void main(String[] args) throws Exception { 

    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
 StringTokenizer tokenizer;
 tokenizer=new StringTokenizer(reader.readLine());
 int n = Integer.parseInt(tokenizer.nextToken());
 int m=Integer.parseInt(tokenizer.nextToken());
 tokenizer=new StringTokenizer(reader.readLine());
 int []num=new int[n];
 int temp;
 for(int i=0;i<n;i++)
 {
     num[i]=Integer.parseInt(tokenizer.nextToken());
 }
 Arrays.sort(num);
 boolean [][]can=new boolean[10002][102];
can[n][0] = true;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0;j <= m; ++j) {
            can[i][j] = can[i + 1][j] || ((j >= num[i]) && can[i + 1][j - num[i]]);
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            System.out.print(can[i][j]+" ");
        }
        System.out.println();
    }

    if (can[0][m]) {
        boolean have = false;
        for (int i = 0; (i < n) && (m >= num[i]); ++i) {
            if (can[i + 1][m - num[i]]) {
                if (have) {
                    System.out.print(" ");
                }
                else {
                    have = true;
                }
                System.out.print(num[i]);
                m -= num[i];
            }
        }
        //puts("");
    }
    else {
        System.out.println("No Solution");
    }

}

}

编辑于 2018-11-20 20:05:07 回复(0)
酒千觞头像 酒千觞 
N,M=map(int,input().split())
c=list(map(int,input().split()))
c.sort()
F=[None]*(M+1)
F[0]=[]
for i in range(N):
    for j in range(M,coin[i]-1,-1):
        t=F[j-c[i]][:]+[c[i]] if F[j-c[i]]!=None else None
        F[j]=F[j] if t==None else t if F[j]==None else min(F[j],t)
if F[M]!=None:
    print(' '.join(map(str,F[M])))
else:
    print('No Solution')
难过，难过，难过
编辑于 2018-09-01 12:31:15 回复(0)
一将难成头像 一将难成 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
	private static int m;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		m = in.nextInt();
		int[] money = new int[n];
		for (int i = 0; i < n; i++)
			money[i] = in.nextInt();
		Arrays.sort(money);
		ArrayList<ArrayList<Integer>> result = new ArrayList<>();
		ArrayList<Integer> subList = new ArrayList<>();
		back(result, subList, money, 0, 0);
		if (result.size() == 0)
			System.out.println("No Solution");
		else {
			List<Integer> res = result.get(0);
			for (int i = 0; i < res.size() - 1; i++)
				System.out.print(res.get(i) + " ");
			System.out.println(res.get(res.size() - 1));
		}
	}

	private static boolean flag;

	public static void back(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> subList, int[] arr, int start,
			int sum) {
		if (flag)
			return;
		if (start > arr.length || sum > m)
			return;
		if (sum == m) {
			flag = true;
			result.add(new ArrayList<>(subList));
			return;
		}
		for (int i = start; i < arr.length; i++) {
			subList.add(arr[i]);
			back(result, subList, arr, i + 1, sum + arr[i]);
			subList.remove(subList.size() - 1);
			if (sum + arr[i] > m)
				break;
		}
	}

}
回溯算法，好像没看到有人用贴出来分享一下。
发表于 2017-09-08 16:01:03 回复(1)
C/C++
已注销头像 已注销 

	
	

		深度优先搜索
	


	

		#include<iostream>
	


	

		#include<vector>
	


	

		#include<algorithm>
	


	

		using namespace std;
	


	

		vector<int> last;
	


	

		void dfs(vector<vector<int>> &result,int target,vector<int> path,int length,int start,vector<int> &number)
	


	

		{
	


	

		if(length==target)
	


	

		{
	


	

		result.push_back(path);
	


	

		return;
	


	

		}
	


	

		if(length>target)return;
	


	

		if(target-length>last[start])return;
	


	

		for(int i=start+1;i<number.size();i++)
	


	

		{
	


	

		if(number[i]+length>target)break;
	


	

		path.push_back(number[i]);
	


	

		dfs(result,target,path,length+number[i],i,number);
	


	

		if(result.size()>0)break;
	


	

		path.pop_back();
	


	

		}
	


	

		}
	


	

		int main()
	


	

		{
	


	

		int n;
	


	

		int m;
	


	

		cin>>n>>m;
	


	

		vector<int> number;
	


	

		for(int i=0;i<n;i++)
	


	

		{
	


	

		int temp;
	


	

		cin>>temp;
	


	

		number.push_back(temp);
	


	

		}
	


	

		sort(number.begin(),number.end());
	


	

		int sum=0;
	


	

		last=vector<int>(n,0);
	


	

		for(int i=number.size()-1;i>=0;i--)
	


	

		{
	


	

		last[i]=sum;
	


	

		sum+=number[i];
	


	

		}
	


	

		vector<vector<int>> result;
	


	

		for(int i=0;i<number.size();i++)
	


	

		{
	


	

		if(number[i]>m)continue;
	


	

		vector<int> path;
	


	

		path.push_back(number[i]);
	


	

		dfs(result,m,path,number[i],i,number);
	


	

		if(result.size()>0)break;
	


	

		}
	


	

		if(result.size()==0)
	


	

		{
	


	

		cout<<"No Solution";
	


	

		}
	


	

		else
	


	

		{
	


	

		vector<int> v=result[0];
	


	

		for(int i=0;i<v.size()-1;i++)
	


	

		{
	


	

		cout<<v[i]<<" ";
	


	

		}
	


	

		cout<<v.back();
	


	

		}
	


	

		return 0;
	


	

		}

发表于 2017-09-05 13:07:07 回复(0)
RicardoZi头像 RicardoZi 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10001;
const int maxv = 101;
int w[maxn], dp[maxv] = {0};
bool choice[maxn][maxv], flag[maxn];
bool compare(int a, int b){
	return a > b;
}

int main(){
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++)
		scanf("%d", &w[i]);
	sort(w + 1, w + n + 1, compare);
	for(int i=1; i<=n; i++){
		for(int v=m; v>=w[i]; v--){
			if(dp[v] <= dp[v-w[i]] + w[i]){
				dp[v] = dp[v-w[i]] + w[i];
				choice[i][v] = true;
			}
			else
				choice[i][v] = false;
		}
	}
	if(dp[m] != m) printf("No Solution\n");
	else{
		int k = n, num = 0, v=m;
		while(k >= 0){
			if(choice[k][v] == true){
				flag[k] = true;
				v -= w[k];
				num ++;
			}
			else flag[k] = false;
			k--;
		}
		for(int i=n; i>=1; i--){
			if(flag[i] == true){
				printf("%d", w[i]);
				num --;
				if(num > 0) printf(" ");
			}
		}
		printf("\n");
	}
	return 0;
}

发表于 2017-08-29 00:54:52 回复(0)
cuttler头像 cuttler
我的代码在pat上有一个测试点过不了
代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N, M;
const int maxn = 10000 + 5;
int c[maxn];

int cal()
{
vector<int> v;
int sum = 0;
int i = 0;
while (1)
{
if (sum == M)
break;
if (i >= N)//不可放在循环结束，否则若循环结束时刚好满足sum==M的解会错过
return -1;
if (c[i] + sum <= M)
{
sum += c[i];
v.push_back(i);
i++;
}
else if (v.size() != 0)
{
int tmp = v.back();
v.pop_back();
sum -= c[tmp];
i = tmp + 1;
}
else
return -1;
}

for (auto k = 0;k < v.size();k++)
{
if (k != 0)
cout << " ";
cout << c[v[k]];
}
cout << endl;
return 0;
}

int main()
{
//freopen("t1.txt", "r", stdin);
cin >> N >> M;
for (int i = 0;i < N;i++)
cin >> c[i];
sort(c, c + N);
if (cal() == -1)
cout << "No Solution"<<endl;

return 0; 
}

发表于 2017-08-26 17:05:43 回复(0)
言午111111111头像 言午111111111 

	//这题用0-1背包问题,不过用硬币的组合替换了原来背包问题的权值





	 





	/*





	动态规划举例:





	8 9





	5 9 8 7 2 3 4 1





	 





	先排序,然后依次处理1,2,3,4...





	 





	和:0 1 2 3 4 5 6 7 8 9





	组成方法:





	处理1





	序号  0   1  2  3  4  5  6  7  8  9





	dp   () (1) () () () () () () () ()





	 





	处理2





	序号  0   1   2    3   4  5  6  7  8  9





	dp   () (1) (2) (1,2) () () () () () ()





	 





	更新序号i时根据序号i-2,i-2存在则有dp[i-2].push_back(2)的组成方式





	然后看看这种方式是否最优,是则加到dp[i],下面同理





	 





	处理3





	序号  0   1   2    3    4      5     6       7   8  9





	dp   () (1) (2) (1,2)  (1,3)  (2,3) (1,2,3) () () ()





	 





	 





	....





	 





	另外遍历j时是倒序的,跟新i是需要上个硬币的dp[i-2],正序dp[i-2]被更新为





	这个硬币的了





	*/





	 





	 





	 





	#include<bits/stdc++.h>





	 





	using namespace std;





	 





	//





	vector<int> MySmall(vector<int> &a, vector<int> &b){





	 





	    //空的返回另一一个





	    if(a.empty())return b;





	    if(b.empty())return a;





	    int p = 0;





	    while (p < a.size() && p < b.size()){





	        if (a[p] < b[p])return a;





	        if (a[p] > b[p])return b;





	        p++;





	    }





	     





	    return a.size()>b.size() ? a : b;





	}





	 





	int main(){





	 





	    ios::sync_with_stdio(false);





	    int N, M;





	    vector<int> v;





	    cin >> N >> M;





	 





	    v.resize(N);





	 





	    for (int i = 0; i<N; i++){





	        cin >> v[i];





	    }





	 





	    sort(v.begin(), v.end());





	 





	 





	     





	    vector<vector<int>> dp(M+1);//dp[j]:和j的最small的组合





	 





	 





	    for (int i = 0; i < N;i++){





	        int n = v[i];





	        for (int j = M; j >= n; j--){





	            vector<int> tmp = dp[j - n];





	             





	            tmp.push_back(n);





	            if (tmp.size() > 1 || n == j){





	                    dp[j] = MySmall(dp[j], tmp);





	            }





	 





	 





	             





	        }





	 





	    }





	 





	    if (dp[M].empty()){





	        cout << "No Solution";





	    }





	    else{





	        for (int i = 0; i<dp[M].size() - 1; i++){





	            cout << dp[M][i] << " ";





	        }





	        cout << dp[M].back();





	    }





	 





	    return 0;





	}





	 

发表于 2017-07-14 15:46:53 回复(0)
提交观点

问题信息

动态规划
难度：
21条回答 8747浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号