2363: 【入门】码头的集装箱

内存限制：512 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：13 解决：8

题目描述

码头上停泊一艘远洋轮船，轮船可以装下 c 吨的货物，码头上有 n 个集装箱需要运走，已知第 i 个集装箱的重量为w i 。
请你编程计算，在不超出轮船最大载重量的情况下，该轮船最多可以运走多少吨的集装箱。（注意：单个集装箱不能拆开运送，对于每个集装箱来说，要么整个运到轮船上，要么不运）

输入

第一行有 2 个正整数 n 和 c 。n 是集装箱数，c 是轮船的载重量。
第 2 行中有 n 个正整数，表示集装箱的重量（0<n<10000,0<c<32767)。

输出

计算出的最大装载重量输出。

样例输入 复制 

5 10
7 2 6 5 4

样例输出 复制 

10

提示


#include<bits/stdc++.h>
using namespace std;
#define N 32770
int n,c,ai,i,j;
long long dp[N],ans=0;
int main(){
	cin>>n>>c;
	for(i=1;i<=n;i++){
		cin>>ai;
		for(j=c;j>=ai;j--){
        	dp[j]=max(dp[j],dp[j-ai]+ai);
		}
	}
	cout<<dp[c];
	return 0;
}



思路：dp[j]代表重量 j 是否可以凑出来。最后从 c 往下找第一个为 true 的 j 就是答案。

逻辑说明

  1. dp[0]=true：重量 0 一定可以凑出来（什么都不装）
  2. 遍历每个集装箱，倒序更新，标记哪些总重量可以凑出来
  3. 从最大载重 c 向下遍历，第一个dp[j]==true，就是不超过 c 的最大可凑重量。 


#include <iostream>
using namespace std;

const int MAXC = 32767;
bool dp[MAXC + 1];   // 普通一维数组

int main()
{
    int n, c;
    cin >> n >> c;

    dp[0] = true;
    // 初始化其余为false
    for(int i = 1; i <= c; i++){
        dp[i] = false;
    }

    for(int i = 1; i <= n; i++)
    {
        int w;
        cin >> w;
        // 01背包，倒序
        for(int j = c; j >= w; j--)
        {
            if(dp[j - w])
            {
                dp[j] = true;
            }
        }
    }

    // 找最大可以凑出来的重量
    int ans = 0;
    for(int j = c; j >= 0; j--)
    {
        if(dp[j])
        {
            ans = j;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

来源/分类

提交提交记录统计露一手!