Instructions: All answers must be proved: it is not sucient to simply state the
ID: 3843285 • Letter: I
Question
Instructions: All answers must be proved: it is not sucient to simply state the answer. All answers must be written in your own words.
Treat single arithmetic operations (addition, subtraction, multiplication, and division) as constant time operations.
Note: I am posting this question second time and I did not satisy from first one. Please answer me clearly according to statement. Thank You!
Problem: You have a set of coins. Each coin i has value vi. Your goal is to nd a set of coins with total value exactly equal to V . You can use only one copy of each coin.
Design a dynamic programming algorithm to determine whether it is possible to accomplish this. You don’t need to output which coins are used, just whether it is possible or not. Hint: this is similar to, but not the same as, the knapsack problem without item repetition. Like we did in the edit distance problem and the knapsack without repetition problem, you will need a 2-dimensional DAG. Dene P(i,W) = True if you can get value W using coins 1,...,i.
How do you calculate P(i,W) using subproblems?
Explanation / Answer
import java.util.*;
public class Main {
public static void main(String[] args) {
int coins[] = {2,3,7,15};
final int TARGET = 20;
//Let dp[i][w] defines whether the sum 'w' can be achieved using the first i coins. We are going to fill this table
boolean dp[][] = new boolean[coins.length][TARGET+1];
//This loop for initialization
for(int i=0;i<coins.length;i++){
//the sum, coins[i] can definitely be obtained by the first i coins (using ith coin only). So, dp[i][coins[i]] = true
if(coins[i]<=TARGET)
dp[i][coins[i]] = true;
//0 can be obtained by first i coins (with no coin)
dp[i][0] = true;
}
//Here we are filling the table
for(int i=1;i<coins.length;i++){
for(int j=1;j<=TARGET;j++){
//We can obtain the sum j using the first i coins, if we can obtain the sum j using the first i-1 coins.
dp[i][j] = dp[i][j]||dp[i-1][j];
//We can obtain the sum 'j' using the first i coins if we can obtain the sum j-coins[i] using the first i-1 coins.
dp[i][j] = dp[i][j]||(((j-coins[i])<=TARGET&&j>=coins[i])?dp[i-1][j-coins[i]]:false);
}
}
for(int i=0;i<=TARGET;i++){
System.out.println("SUM : "+i+ " POSSIBLE : "+dp[coins.length-1][i]);
}
}
}
OUTPUT :
SUM : 0 POSSIBLE : true
SUM : 1 POSSIBLE : false
SUM : 2 POSSIBLE : true
SUM : 3 POSSIBLE : true
SUM : 4 POSSIBLE : false
SUM : 5 POSSIBLE : true
SUM : 6 POSSIBLE : false
SUM : 7 POSSIBLE : true
SUM : 8 POSSIBLE : false
SUM : 9 POSSIBLE : true
SUM : 10 POSSIBLE : true
SUM : 11 POSSIBLE : false
SUM : 12 POSSIBLE : true
SUM : 13 POSSIBLE : false
SUM : 14 POSSIBLE : false
SUM : 15 POSSIBLE : true
SUM : 16 POSSIBLE : false
SUM : 17 POSSIBLE : true
SUM : 18 POSSIBLE : true
SUM : 19 POSSIBLE : false
SUM : 20 POSSIBLE : true