Subproblem definition : Define a two-dimensional array b, among b[i][j] Before presentation i Can I exchange the price for one currency j, It means the first one i The face value of each currency , The first i There are two ways to use a currency , If you use , be b[i][j]=b[i-1][j-], If not used , be b[i][j]=b[i-1][j]

Recursion :

Initial value setting ：

The order of solution ：

Solve the array from small to large by subscript b The value of each line , Finally, two-dimensional arrays b The element value in the lower right corner of is the final solution .

``` package org.xiu68.ch06.ex7;

public class Ex6_18 {

// The face value is x1,x2,x3,...,xn Can I exchange my coins for the price v, Each coin can only be used once ( The solution is a little bit like 0-1 knapsack problem )
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] x=new int[]{1,3,5,6};
for(int i=0;i<=20;i++)
convertChange(x, i);
}
//coin: The denomination of the coin
//v: The price to be exchanged
public static void convertChange(int[] x,int v){
boolean[][] b=new boolean[x.length+1][v+1];       //b[i][j] Before use i Can I exchange the price for one currency j
for(int i=0;i<=x.length;i++)
b[i][0]=true;                    // It means the price can be exchanged in any currency 0
for(int j=1;j<=v;j++)
b[0][j]=false;                     // No coin can be exchanged for anything larger than 0 The price of

for(int i=1;i<=x.length;i++){
for(int j=1;j<=v;j++){

boolean use=false;
if(j>=x[i-1])                        // Price j To be greater than or equal to i Only one currency can be used i Currency exchange
use=b[i-1][j-x[i-1]];              // Use the i In the case of one currency  ,x[i-1]: The first i Currency subscript is i-1
boolean nuse=b[i-1][j];                // Don't use the second i In the case of a coin

if(use || nuse)                       // As long as there is one situation that can be exchanged, then i One currency can change the price j
b[i][j]=true;
else
b[i][j]=false;
}//for2
}//for1

System.out.print(v+":"+b[x.length][v]);

if(b[x.length][v]){
System.out.print("  use: ");
for(int i=x.length,j=v;i>0 && j>0;){
if(j>=x[i-1] && b[i-1][j-x[i-1]]){             // Using the second i Currency
System.out.print(x[i-1]+" ");
j=j-x[i-1];
i--;
}else{                                            // No use of the second i Currency
i--;
}
}//for
}
System.out.println();
}
// Running results ：
/*0:true  use:
1:true  use: 1
2:false
3:true  use: 3
4:true  use: 3 1
5:true  use: 5
6:true  use: 6
7:true  use: 6 1
8:true  use: 5 3
9:true  use: 6 3
10:true  use: 6 3 1
11:true  use: 6 5
12:true  use: 6 5 1
13:false
14:true  use: 6 5 3
15:true  use: 6 5 3 1
16:false
17:false
18:false
19:false
20:false*/
}```

## Ex 6_18 The limited exchange of coins _ More articles on assignment 7

1. Ex 6_17 An unlimited number of coins _ The seventh assignment

Subproblem definition : Define an array b, The size is one more element than the size of the exchange price , among b[i] It means whether we can use the face value of x1,x2,x3,..,xn The coin exchange rate of i. Recursion : Initial value setting : set up b[0]=true The order of solution : By subscript from ...

2. Ex 6_19 At most k A coin for a price _ The seventh assignment

Subproblem definition : Define a two-dimensional array b, among b[i][j] To express with i Can a coin change the price j, It means the first one i The face value of each currency , Recursion : Initial value setting : The order of solution : Solve the array from small to large by subscript b The value of each column , Finally, two-dimensional arrays b Of ...

3. Ex 6_26 Sequence alignment ..._ The seventh assignment

4. Ex 6_23 A production system consists of n There are three stages of sequential execution ..._ The seventh assignment

5. Ex 6_16 Second hand sales problems _ The seventh assignment

that will do Subproblem definition : Define an array B(S,j), among B(S,j) That means in a subset S The ending position in is j The maximum return value of the subproblem of , among j There are two kinds of situations in the previous location of , The first is an auction Another situation is starting from home . Recursion : first ...

6. ArcGIS for Desktop Introductory tutorial _ Chapter vii. _ Use ArcGIS Do spatial analysis - ArcGIS You know - new generation ArcGIS Question answering community

original text :ArcGIS for Desktop Introductory tutorial _ Chapter vii. _ Use ArcGIS Do spatial analysis - ArcGIS You know - new generation ArcGIS Question answering community 1 Use ArcGIS Do spatial analysis 1.1 GIS Basis of analysis G ...

7. Money exchange issues _ Completely backpack &amp;&amp; Split &amp;&amp; The generating function

ps: I used Sina , But the layout of the code is not very good , So use blog Garden , Allow me to move the code from August , Start over from here , I hope I can always witness my growth here . Time Limit: 2000/1000 MS (Jav ...

8. Netease cloud classroom _C Advanced language programming _ Week 7 ： file ： File access 、 Format input and output 、 Binary input and output

7.1 file 7.2 Underlying operations 7.1 file Formatted input and output printf %[flags][width][.prec][hIL]type Flag meaning - Align left + Put... In the front + or - (space) ...

9. .Net The basic chapter _ Learning notes _ Seventh days _ The generation of random numbers

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.T ...

## Random recommendation

1. jquery The principle of chain call

(1). call chaining \$("#mybtn").css("width","100px") .css("height",&quo ...

2. C++11 lambda The understanding of the

C++11 Of lambda The expression specification is as follows : [ capture ] ( params ) mutable exception attribute -> ret { body } (1) [ ...

3. BZOJ1086 [SCOI2005] The Royal Union

Description “ more than ” The king of man wants to reorganize his country . He wants to divide his country into several provinces , Each province is made up of one of their royal federations To manage . His country has n Cities , The number is 1..n. Some cities are connected by roads , Any two ...

4. SVG Format

SVG Format edit Objective record summary brief introduction advantage example show 1 summary SVG Format SVG Is a kind of use XML The language of definition , Used to describe two-dimensional vectors and vectors / Grid graphics .SVG Provides 3 There are two types of graphic objects : Vector graphics (vectorgr ...

5. Processor Speculative &amp; pipeline

https://en.wikipedia.org/wiki/Instruction-level_parallelism https://en.wikipedia.org/wiki/Instructio ...

6. c# You can set transparency Panel Components

using System; using System.Collections.Generic; using System.ComponentModel; using System.Drawing; u ...

7. Linux Lower access LAN It is specified in IP Of MAC（ Physical address ）

// all.h// 2005/06/20,a.m. wenxy #ifndef _ALL_H#define _ALL_H #include <memory.h>#include < ...

8. web Simple select all and reverse select

<html> <body> <table> <tr> <th><input type="checkbox" onc ...

9. sass establish web Project environment steps

1)npm establish web Front end project environment steps 1. New folder , Enter... Under this file cmd Console 2. Enter the command npm init enter 3.name: Name only supports lowercase , Uppercase is not supported , Just change the name from upper case to lower case 4.version ...

10. 【CentOS 7】CentOS7 And CentOS6 The difference between

Preface centos7 And 6 The biggest difference between them is the initialization technology ,7 The initialization technique used is Systemd, Parallel mode of operation , Apart from that , Service startup . Boot file . Network command and so on , All say 6 Somewhat different . One . System initial ...