ssnlj

ssnlj 文本复制页面

public class Knapsack {
    public static void main(String[] args) {
        // 商品数据：重量、价值
        int[] w = {0, 2, 3, 4, 1, 3}; // 索引1~5
        int[] v = {0, 3, 4, 5, 2, 6};
        int capacity = 8;
        int n = 5;

        // dp[j] 表示容量j时的最大价值，压缩为一维数组
        int[] dp = new int[capacity + 1];
        // 记录选择方案，choice[i][j]表示在容量j时是否选了第i件
        boolean[][] choice = new boolean[n + 1][capacity + 1];

        // 动态规划
        for (int i = 1; i <= n; i++) {
            for (int j = capacity; j >= w[i]; j--) { // 逆序保证0-1特性
                if (dp[j] < dp[j - w[i]] + v[i]) {
                    dp[j] = dp[j - w[i]] + v[i];
                    choice[i][j] = true;
                }
            }
        }

        // 回溯选中的商品
        int remain = capacity;
        StringBuilder items = new StringBuilder();
        for (int i = n; i >= 1; i--) {
            if (choice[i][remain]) {
                items.insert(0, "商品" + i + "、");
                remain -= w[i];
            }
        }
        // 删除末尾多余的顿号
        if (items.length() > 0) items.setLength(items.length() - 1);
        
        // 计算总重量
        int totalWeight = capacity - remain;
        
        System.out.println("最优总价值：" + dp[capacity] + "万元");
        System.out.println("装载方案：" + items);
        System.out.println("总重量：" + totalWeight + "吨（≤8吨）");
    }
}
----------------
	public class GreedyChange {
	    public static void main(String[] args) {
	        // ========== 1. 数据初始化 ==========
	        
	        int amount = 186;                     
	        // 待兑换的总金额，单位：元。
	        // 这是一个固定输入，实际应用中可改为 Scanner 读取用户输入。
	        
	        int[] denom = {100, 50, 20, 10, 5, 1}; 
	        // 可用面额数组，必须按从大到小降序排列。
	        // 这是贪心算法正确性的前提：先尝试大面额，再依次降级。
	        // 若改为升序 {1,5,10,...}，算法会优先使用大量 1 元，结果错误。
	        
	        int[] count = new int[denom.length];   
	        // count[i] 记录第 i 种面额（即 denom[i]）最终使用了多少张。
	        // 初始值全为 0，Java 自动完成零初始化。

	        // ========== 2. 贪心核心计算 ==========
	        
	        int remain = amount;   
	        // remain：剩余待兑换金额。初始为 186，每轮循环后递减。
	        // 使用 remain 而非直接修改 amount，保留原始金额用于最后输出验证。
	        
	        int totalBills = 0;    
	        // totalBills：累计使用的纸币总张数。
	        // 每确定一种面额的张数，就累加进来，最后输出。

	        // 贪心策略：遍历面额，从大到小，每次"能拿多少拿多少"
	        for (int i = 0; i < denom.length; i++) {
	            // i = 0 时 denom[0] = 100，先尝试 100 元；
	            // i = 1 时 denom[1] = 50，再尝试 50 元，以此类推。
	            
	            count[i] = remain / denom[i];   
	            // 整数除法，自动得到"当前面额最多能用几张"。
	            // 例如：remain = 186 时，186 / 100 = 1（张 100 元）；
	            //      remain = 86  时，86  / 50  = 1（张 50 元）；
	            //      remain = 36  时，36  / 20  = 1（张 20 元）；
	            //      remain = 16  时，16  / 10  = 1（张 10 元）；
	            //      remain = 6   时，6   / 5   = 1（张 5 元）；
	            //      remain = 1   时，1   / 1   = 1（张 1 元）。
	            
	            remain %= denom[i];              
	            // 取模运算，得到"使用完当前面额后还剩多少钱"。
	            // 例如：186 % 100 = 86，表示用掉 1 张 100 元后还剩 86 元。
	            // 这行代码等价于：remain = remain - count[i] * denom[i]；
	            // 但取模运算更简洁、效率更高。
	            
	            totalBills += count[i];
	            // 把当前面额使用的张数加到总张数中。
	            // 例如：第一轮 totalBills = 0 + 1 = 1。
	        }
	        // 循环结束后，remain 必定为 0（因为最小面额是 1 元，总能凑整）。
	        // totalBills = 1+1+1+1+1+1 = 6 张。

	        // ========== 3. 结果输出 ==========
	        
	        System.out.println("兑换金额：" + amount + "元");
	        // 打印原始金额，用于与用户确认。
	        
	        System.out.println("最少张数：" + totalBills + "张");
	        // 输出贪心算法得到的总张数。
	        
	        System.out.print("兑换方案：");
	        for (int i = 0; i < denom.length; i++) {
	            if (count[i] > 0) {
	                // 只打印实际使用过的面额，过滤掉 0 张的情况。
	                // 例如 count[0]=1，打印"100元×1张"；
	                // count[5]=1，打印"1元×1张"。
	                System.out.print(denom[i] + "元×" + count[i] + "张、");
	            }
	        }
	        System.out.println(); 
	        // 换行，清空 System.out.print 的缓冲区，避免与下一行输出粘连。
	        
	        System.out.println("总验证：" + amount + "元 = " + amount + "元");
	       
	    }
	}
快捷键：Ctrl+A 全选文本，Ctrl+C 一键复制