动态规划 01背包模板题

素颜马尾好姑娘i 2024-01-11 06:46 36阅读 0赞

### 1414: 集装箱装载 ###

时间限制: 1 Sec 内存限制: 128 MB  
提交: 45 解决: 27  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### 题目描述 ###

有一批共n个集装箱要装上艘载重量为c的轮船，其中集装箱i的重量为wi。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。

### 输入 ###

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

### 输出 ###

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

### 样例输入 ###

### 样例输出 ###

### 提示 ###

### 来源 ###

[动态规划-背包问题][-]

<table> 
 <tbody> 
  <tr> 
   <td><span style="color:#000000;"><strong>题目智能推荐</strong></span></td> 
  </tr> 
 </tbody> 
</table>

01背包问题

不得不说测试数据真水。

#include<iostream>
    #include<cstring>
    #include<algorithm> 
    using namespace std;
    int dp[10001][2770];
    int a[10001];
    int cmp(int x,int y)
    {
    	return x>y;
    }
    int main()
    {
    	
    	int n,c;
    	int i,j;
        scanf("%d %d",&n,&c);
        {
        	int max=0;
        	
        	memset(dp,0,sizeof(dp));
        	for(i=1;i<=n;i++)
        	{
        		scanf("%d",&a[i]);
        		
    		}
        	sort(a+1,a+1+n,cmp);
        	for(i=1;i<=n;i++)
        	{
        		for(j=1;j<=c;j++)
        		{
        			dp[i][j]=dp[i-1][j];
        			if(a[i]<=j)
        			{
        				dp[i][j]=dp[i][j]>dp[i-1][j-a[i]]+a[i]?dp[i][j]:dp[i-1][j-a[i]]+a[i];
    				}
    				
    			}
    			
    		}
    		printf("%d\n",dp[n][c]);
    	}
    	return 0;
    }

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1414
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1414
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1414
[-]: http://xyoj.xynu.edu.cn/problemset.php?search=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98