生活随笔
收集整理的這篇文章主要介紹了
NYOJ 49 开心的小明
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
開心的小明 時間限制：
1000 ?ms ?|? 內(nèi)存限制：
65535 ?KB 難度：
4
描述
小明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N 元錢就行”。今天一早小明就開始做預(yù)算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。于是，他把每件物品規(guī)定了一個重要度，分為5 等：用整數(shù)1~5 表示，第5 等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過N 元（可以等于N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設(shè)第j 件物品的價格為v[j]，重要度為w[j]，共選中了k 件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設(shè)計一個滿足要求的購物單. 輸入第一行輸入一個整數(shù)N(0<N<=101)表示測試數(shù)據(jù)組數(shù) 輸出每組測試數(shù)據(jù)輸出只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的 樣例輸入 1
1000 5
800 2
400 5
300 5
400 3
200 2 樣例輸出 3900 背包問題也是動態(tài)規(guī)劃問題！ 解題思路： 首先為了簡化問題，我們把1000，800 ··· 200簡化為10,8 ··· 2 ！ 第一步：初始化10個背包 dp[0]=0:表示可能會出現(xiàn)的價格為0的狀態(tài)，初始值為0 dp[1]=0:表示可能會出現(xiàn)的價格為1的狀態(tài)，初始值為0 dp[2]=0:表示可能會出現(xiàn)的價格為2的狀態(tài)，初始值為0 dp[3]=0:表示可能會出現(xiàn)的價格為3的狀態(tài)，初始值為0 dp[4]=0:表示可能會出現(xiàn)的價格為4的狀態(tài)，初始值為0 dp[5]=0:表示可能會出現(xiàn)的價格為5的狀態(tài)，初始值為0 dp[6]=0:表示可能會出現(xiàn)的價格為6的狀態(tài)，初始值為0 dp[7]=0:表示可能會出現(xiàn)的價格為7的狀態(tài)，初始值為0 dp[8]=0:表示可能會出現(xiàn)的價格為8的狀態(tài)，初始值為0 dp[9]=0:表示可能會出現(xiàn)的價格為9的狀態(tài)，初始值為0 dp[10]=0:表示可能會出現(xiàn)的價格為10的狀態(tài)，初始值為0 第二步：分析給出的每組數(shù)據(jù) 第一組：8 2；假如說把價格為8重要程度為2的物品裝進背包，那么此時背包會出現(xiàn)哪幾種狀態(tài)呢？很明顯，可能會出現(xiàn)背包從dp[0]轉(zhuǎn)移到dp[8]，dp[1]轉(zhuǎn)移到dp[9],dp[2]轉(zhuǎn)移到dp[10]這三個狀態(tài)；那么dp[8],dp[9],dp[10]這三個狀態(tài)是保留還是舍去呢？此時肯定要比較在這個狀態(tài)轉(zhuǎn)移之前和狀態(tài)轉(zhuǎn)移之后，我們更想要哪個狀態(tài)？所以需要寫成dp[10]=Max(dp[10],dp[10-8]+2*8);dp[10]表示狀態(tài)轉(zhuǎn)移之前的狀態(tài)，dp[10-8]+2*8表示狀態(tài)轉(zhuǎn)移之后的狀態(tài)！同樣，有dp[9]=Max(dp[9],dp[9-8]+2*8);dp[8]=Max(dp[8],dp[8-8]+2*8); 第二組：4 5；有上述可列出：dp[10]=Max(dp[10],dp[10-4]+4*5); dp[9]=Max(dp[9],dp[9-4]+4*5); ··· ;dp[4]=Max(dp[4],dp[4-4]+4*5); 依次類推······ 最后dp[10]的值即為要求得的結(jié)果！ AC碼： #include<stdio.h>
#include<string.h>
struct node
{int v;int p;
}num[25];
int max(int x,int y)
{return x>y?x:y;
}
int main()
{int N;int dp[30003];scanf("%d",&N);while(N--){int n,m,i,j;scanf("%d%d",&n,&m);memset(dp,0,sizeof(dp));for(i=0;i<m;i++){scanf("%d%d",&num[i].v,&num[i].p);}for(i=0;i<m;i++){for(j=n;j>=num[i].v;j--)dp[j]=max(dp[j-num[i].v]+num[i].v*num[i].p,dp[j]);}printf("%d\n",dp[n]);}return 0;
}
總結(jié)
以上是生活随笔 為你收集整理的NYOJ 49 开心的小明 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
