背包问题

爱被打了一巴掌 2022-02-05 01:37 270阅读 0赞

时间限制：1秒

空间限制：32768K

A 国的手机号码由且仅由 N 位十进制数字(0-9)组成。一个手机号码中有至少 K 位数字相同则被定义为靓号。A 国的手机号可以有前导零，比如 000123456 是一个合法的手机号。  
小多想花钱将自己的手机号码修改为一个靓号。修改号码中的一个数字需要花费的金额为新数字与旧数字之间的差值。比如将 1 修改为 6 或 6 修改为 1 都需要花 5 块钱。  
给出小多现在的手机号码，问将其修改成一个靓号，最少需要多少钱？

输入描述:  
第一行包含2个整数 N、K，分别表示手机号码数字个数以及靓号至少有 K 个数字相同。  
第二行包含 N 个字符，每个字符都是一个数字(‘0’-‘9’)，数字之间没有任何其他空白符。表示小多的手机号码。  
数据范围：  
2 <= K <= N <= 10000

输出描述:  
第一行包含一个整数，表示修改成一个靓号，最少需要的金额。  
第二行包含 N 个数字字符，表示最少花费修改的新手机号。若有多个靓号花费都最少，则输出字典序最小的靓号。

输入例子1:  
6 5  
787585

输出例子1:  
4  
777577

例子说明1:  
花费为4的方案有两种：777577与777775，前者字典序更小。

package bishi;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.Scanner;
    import java.util.Vector;
    
    import javax.net.ssl.SNIHostName;
    import javax.print.attribute.standard.RequestingUserName;
    import javax.xml.ws.wsaddressing.W3CEndpointReference;
    class struct{
    	int first;
    	String second;
    }
    class Test {
    	int N;
    	int K;
    	int[] tel;
    	String secondString;
    	void getIN() {
    		Scanner scanner = new Scanner(System.in);
    		N = scanner.nextInt();
    		K = scanner.nextInt();
    		String next = scanner.next();
    
    		char[] charArray = next.toCharArray();
    		tel = new int[N];
    		for (int i = 0; i < charArray.length; i++) {
    			tel[i] = charArray[i] - '0';
    		}
    	}
    
    	void wai() {
    		int minint = Integer.MAX_VALUE;
    		List<struct>result = new ArrayList<struct>();
    		for (int k = 0; k < 10; k++) {
    			struct element = new struct();
    			int t = nei(k);
    			element.first = t;
    			element.second = this.secondString;
    			result.add(element);
    			System.out.println(k+":" +t);
    		}
    		int standard = -1;
    		for(int i = 0; i < 10; i++) {
    			if(minint>result.get(i).first) {
    				minint = result.get(i).first;
    				standard = i;
    			}else if (minint==result.get(i).first) {
    				if (result.get(standard).second.compareTo(result.get(i).second)>0) {
    					standard = i;
    				}
    			}
    		}
    		System.out.println("结果:");
    		System.out.println(result.get(standard).first);
    		System.out.println(result.get(standard).second);
    	}
    	/*
    	 * 修改为重复的kk，需要修改的总值
    	 * @return 修改总值
    	 * */
    	int nei(int kk) {
    		int hang = N + 1;
    		int lie = K + 1;
    		int max_int = 9999;
    		int[][] map = new int[hang][lie];
    		for (int i = 0; i < hang; i++) {
    			map[i][0] = 0;
    		}
    		for (int i = 1; i < lie; i++) {
    			map[0][i] = max_int;
    		}
    		for (int i = 1; i < hang; i++) {
    			for (int j = 1; j < lie; j++) {
    				map[i][j] = Math.min(map[i - 1][j], map[i - 1][j - 1] + Math.abs(kk - tel[i - 1]));
    			}
    		}
    		//输出map
    		System.out.println("The kk is:"+kk);
    		for(int i = 0; i < hang; i++) {
    			if (i!=0) {
    				System.out.printf("tel[%2d]:%d ",i,Math.abs(kk - tel[i-1]));
    			}else {
    				System.out.print("tel[ %]:% ");
    			}
    			for(int j = 0; j <lie;j++) {
    				System.out.printf("%6d ",map[i][j]);
    			}
    			System.out.print("\n");
    		}
    		int[] temp = new int[N+1];
    		int h = 0;
    		for(int i = N,j = K;i>=1&&j>1;i--) {
    			if((map[i][j]-Math.abs(tel[i-1]-kk)) == map[i-1][j-1]) {
    				j--;
    				temp[h++] = i-1;
    			}
    		}
    		
    		//输出temp
    		for(int i = 0; i < h;i++) {
    			System.out.print(temp[i]);
    		}
    		System.out.println();
    		
    		
    		char[] tempc = new char[N+1];
    		int tou = 0;
    		int wei = h - 1;
    		for(int i = 0; i < N; i++) {
    			
    			if(tou <=wei) {
    				int tempvalue = temp[wei];
    				if (tempvalue == i) {
    					tempc[i] = (char) ('0'+kk);
    					wei--;
    				}else {
    					tempc[i] = (char) ('0'+tel[i]);
    				}
    			}else {
    				tempc[i] = (char) ('0'+tel[i]);
    				
    			}
    		}
    		this.secondString = new String(tempc);
    		System.out.println("first is:"+map[hang-1][lie-1]);
    		System.out.println("secondString is:"+this.secondString);
    		return map[hang-1][lie-1];
    	}
    	
    }
    
    public class LiangHao {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Test test = new Test();
    		test.getIN();
    		test.wai();
    	}
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXdqYWNzZG4_size_16_color_FFFFFF_t_70]  
ps:不能处理存在负数的情况  
这个是个背包问题，从所有差值中找出来和最小的几个，  
在反向找出被选中的值的位置记录下来

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXdqYWNzZG4_size_16_color_FFFFFF_t_70]: /images/20220205/9c00734da25844a8980a9133f804468d.png