问题标题: 1049 装载问题

Question

0

已解决

谢祎恒

中级守护

#include<iostream>
using namespace std;
int n,c,w[110],maxx;
bool used[110];
void DFS(int k,int v)
{
    if(k>n)
    {
        if(v>maxx) maxx=v;
        return ;
    }
    if(v>maxx)
    {
        for(i=0;i<n;i++)
        {
            if(used[i]==false && v)
            {
                used[i]=true;

                used[i]=false;
            }
        }
    }
}
int main()
{
    int i;
    cin>>n>>c;
    for(i=0;i<n;i++)
    {
        cin>>w[i];
    }
    DFS(0,0);
    cout<<maxx;
    return 0;
}

（残缺不齐，漏洞百出的代码）

求解，最好有解释

http://judge.codingtang.com/problem/1049/

Answer 1

已采纳

杨喆

初级守护

搜索回溯做法

首先所有的物品加起来比最大装载重量相等，不需要搜索直接输出；

搜索步骤：v表示当前放物品后的重量，k表示第k次放物品

如果v等于最大装载重量，直接返回，因为这个最大的了；

总共只有k件物品，所以递归边界是当前是第i次放置物品，要小于等于k+1；

当前所放的物品重量为v，然后更新最大的代价；

接着遍历所有可以放的物品，并且保证放入这个物品后不会超过最大装载重量

Answer 2

梁锦程

高级光能

这道题是DP中的装箱问题，本蒟蒻只会用DP写

解题思路：
动态规划的核心思想就是将问题划分为n个存在共同子问题的子问题，并将这些子问题的结果计算并存储起来，一般为数组。
本题使用一维数组dp来记录在当前空间下的最大填充体积，dp[j] ->在体积为j的情况下最大填充为dp[j]；由于在对一个物体来说，它有两种状态，放入箱子dp[i-num[j]]+num[j],或者不放入dp[j],我们需要的是这两者中的较大的一个，即：dp[j] = max(dp[j],dp[i-num[j]]+num[j]);

for(int i = 0; i < m;i++)//将给出的物体放入箱子，防止重复计算
{
for(int j = n; j >= num[i]; j--)//判断物体是否放入箱子
{
dp[j] = max(dp[j],dp[j-num[i]]+num[i]);
}
}

看懂了吗？望采纳！！

Answer 3

陆雨祥

中级守护

1

Answer 4

王梓轩

资深光能

挖坟

问题标题: 1049 装载问题

4 个回答: