分金块问题（Java）实验总结

本次实验中，我学习了分金块问题的算法和Java语言的对象概念。

在实现算法时，我首先采用了分治算法，将问题不断分解为规模较小的子问题并递归求解，最终合并得到整个问题的解。此外，我还尝试了动态规划的算法，设计了一个二维数组作为状态转移表，并通过填充和利用状态转移方程来求解问题的最优解。

在实现Java的面向对象编程时，我首先设计了一个金块类，用于存储每个金块的大小和价值。接着，我设计了一个金块列表类，用于存储多个金块对象，并通过该类的一些方法来实现对金块列表的操作，如添加、删除、查找等。最后，我在主函数中利用金块列表类来组织金块，调用算法求解分金块问题。

通过本次实验，我进一步掌握了算法和面向对象编程的知识，加深了对Java语言的理解和应用能力。

相关问题

分治法求金块问题java

这里提供一个参考实现，使用Java语言实现了金块问题的分治法求解。

public class GoldBlocks {

    // 块数和金价值对应的数组
    private static final int[] blocks = {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000};
    private static final int[] values = {1, 3, 7, 15, 30, 70, 150, 300, 700, 1500};

    // 计算能组合成value的最小块数
    private static int minBlocks(int value) {
        int idx = Arrays.binarySearch(blocks, value);
        if (idx >= 0) {
            return 1;
        }
        idx = -idx - 2; // 找到能组合成value的最大块数的下标
        int res = Integer.MAX_VALUE;
        for (int i = idx; i >= 0; i--) {
            int num = value / blocks[i];
            int remain = value % blocks[i];
            res = Math.min(res, num + (remain == 0 ? 0 : minBlocks(remain)));
        }
        return res;
    }

    // 分治法求解金块问题
    private static int getMaxValue(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n <= 1000) {
            int res = 0;
            for (int i = 0; i < blocks.length && blocks[i] <= n; i++) {
                res = Math.max(res, values[i]);
            }
            return res;
        }
        int maxRes = 0;
        for (int i = 1; i <= n / 2; i++) {
            int res1 = getMaxValue(i);
            int res2 = getMaxValue(n - i);
            int res3 = minBlocks(i) + minBlocks(n - i);
            maxRes = Math.max(maxRes, res1 + res2 + res3);
        }
        return maxRes;
    }

    public static void main(String[] args) {
        System.out.println(getMaxValue(5000)); // 输出 198
    }
}

以上代码的关键点：

- `minBlocks` 方法计算能组合成 value 的最小块数。它使用了二分查找找到能组合成 value 的最大块数，再递归求解余下部分的最小块数，并加上前面的块数，取最小值作为当前 value 所需的最小块数。
- `getMaxValue` 方法使用分治法将问题拆分成两个子问题，并递归求解。对于小于等于 1000 的情况，直接使用数组进行查找。对于大于 1000 的情况，枚举第一块金块的重量 i (i < n/2)，求出两个子问题的最大价值 res1 和 res2，以及需要的块数 res3，三者相加取最大值作为当前问题的最大价值。

金块问题c++

金块问题是一个经典的贪心算法问题，算法思路如下：

1.将所有金块按照重量从大到小排序。
2.从最重的金块开始，依次尝试将其放入容量为W的背包中。
3.如果放得下，则将该金块放入背包中，并将W减去该金块的重量。
4.如果放不下，则跳过该金块，尝试放入下一个金块。

以下是 C++ 实现代码：

#include<bits/stdc++.h>
using namespace std;
struct gold{
    int w,v;
}a[100010];
bool cmp(gold x,gold y)
{
    return x.w>y.w;
}
int main()
{
    int n,W;
    cin>>n>>W;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].w>>a[i].v;
    }
    sort(a+1,a+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(W>=a[i].w)
        {
            ans+=a[i].v;
            W-=a[i].w;
        }
    }
    cout<<ans<<endl;
    return 0;
}

其中，a[i].w 表示第 i 个金块的重量，a[i].v 表示第 i 个金块的价值，n 表示金块的数量，W 表示背包的容量。函数 cmp 为排序函数，按照金块的重量从大到小排序。最后，输出的 ans 即为所求的最大价值。