Problem Description

王小二畢業后從事船運規劃工作，吉祥號貨輪的最大載重量為M噸，有10種貨物可以裝船。第i種貨物有wi噸，總價值是pi。王小二的任務是從10種貨物中挑選若干噸上船，在滿足貨物總重量小于等于M的前提下，運走的貨物的價重比最大。

Input

輸入數據的第一行有一個正整數M(0 <?M?<?10000)，表示所有貨物最大載重量。在接下來的10行中，每行有若干個數（中間用空格分開），第i行表示的是第i種貨物的貨物的總價值pi?,總重量wi。(pi是wi的整數倍，0?<?pi?,?wi?<?1000)

Output

輸出一個整數，表示可以得到的最大價值。

Example Input

100? 10 10 20 10 30 10 40 10 50 10 60 10 70 10 80 10 90 10 100 10

Example Output

550

#include <stdio.h>
#include <stdlib.h>
struct node
{
? ? int pi;
? ? int wi;
? ? int h;
}p[10],t;
int main()
{
? ? int m,i,j;
? ? int k=0;
? ? scanf("%d",&m);
? ? for(i=0;i<10;i++)
? ? {
? ? ? ? scanf("%d%d",&p[i].pi,&p[i].wi);
? ? ? ? p[i].h=p[i].pi/p[i].wi;//每個單價物品；
? ? }
? ? for(i=0;i<9;i++)//冒泡排序；
? ? ? ? for(j=0;j<9-i;j++)
? ? {
? ? ? ? if(p[j].h<p[j+1].h)
? ? ? ? {
? ? ? ? ? ? t=p[j];p[j]=p[j+1];
? ? ? ? ? ? p[j+1]=t;
? ? ? ? }
? ? }
? ? for(i=0;i<10;i++)
? ? {
? ? ? ? if(m>=p[i].wi)
? ? ? ? {
? ? ? ? ? ? k+=p[i].pi;
? ? ? ? ? ? m-=p[i].wi;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? k+=p[i].h*m;
? ? ? ? ? ? break;
? ? ? ? }
? ? }
? ? printf("%d\n",k);
? ? return 0;
}

總結

以上是生活随笔為你收集整理的装船问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。