/*? 016-購物單題目描述王強今天很開心，公司發給N元的年終獎。王強決定把年終獎用于購物，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子： 主件 附件 電腦 打印機，掃描儀 書柜 圖書 書桌 臺燈，文具 工作椅 無 如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有?0?個、?1?個或?2?個附件。附件不再有從屬于自己的附件。王強想買的東西很多，為了不超出預算，他把每件物品規定了一個重要度，分為?5?等：用整數?1?~?5?表示，第?5?等最重要。他還從因特網上查到了每件物品的價格（都是?10?元的整數倍）。他希望在不超過?N?元（可以等于?N?元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第?j?件物品的價格為?v[j]?，重要度為?w[j]?，共選中了?k?件物品，編號依次為?j?1?，?j?2?，……，?j?k?，則所求的總和為： v[j?1?]*w[j?1?]+v[j?2?]*w[j?2?]+?…?+v[j?k?]*w[j?k?]?。（其中?*?為乘號）請你幫助王強設計一個滿足要求的購物單。輸入描述: 輸入的第?1?行，為兩個正整數，用一個空格隔開：N?m （其中?N?（?<32000?）表示總錢數，?m?（?<60?）為希望購買物品的個數。）從第?2?行到第?m+1?行，第?j?行給出了編號為?j-1?的物品的基本數據，每行有?3?個非負整數?v?p?q（其中?v?表示該物品的價格（?v<10000?），?p?表示該物品的重要度（?1?~?5?），?q?表示該物品是主件還是附件。如果?q=0?，表示該物品為主件，如果?q>0?，表示該物品為附件，?q?是所屬主件的編號）輸出描述:輸出文件只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（?<200000?）。輸入例子: 1000?5 800?2?0 400?5?1 300?5?1 400?3?0 500?2?0輸出例子: 2200 */ //c語言版 #include?<stdio.h> int?main(void) {int?N,m;//N為年終獎，m為想購買物品件數int?v[60];//存儲輸入物品價格?int?p[60];//存儲輸入物品的重要度int?q[60];//存儲輸入物品的屬性值，是否為附件還是主件int?f[60][32000];?//存儲價格與重要度乘積的值，作為輸出?int?i,j;//接受輸入?scanf("%d?%d",&N,&m);for(i?=?1;i?<=?m;i++)scanf("%d?%d?%d",&v[i],&p[i],&q[i]);//處理數據 for(i?=?1;i?<=?m;i++?)p[i]?=?v[i]?*?p[i];for(i=1;i<=N;i++){for(j=1;j<=m;j++){if(q[j]==0){if(i<v[j])f[j][i]=0;else{if(f[j-1][i-v[j]]+p[j]>f[j-1][i])f[j][i]=f[j-1][i-v[j]]+p[j];elsef[j][i]=f[j-1][i];}}else{if(i<v[j]+v[q[j]])f[j][i]=0;else?{if(f[j-1][i-v[j]]+p[j]>f[j-1][i])f[j][i]=f[j-1][i-v[j]]+p[j];elsef[j][i]=f[j-1][i];}}}}printf("%d\n",f[m][N]);return?0; ? }

轉載于:https://blog.51cto.com/yutianheji/1829153

總結

以上是生活随笔為你收集整理的016-购物单的全部內容，希望文章能夠幫你解決所遇到的問題。

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