ALGO-31算法訓練 開心的金明（01背包，動態規劃）

金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N 元錢就行”。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N 元。于是，他把每件物品規定了一個重要度，分為5 等：用整數1~5 表示，第5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過N 元（可以等于N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j 件物品的價格為v[j]，重要度為w[j]，共選中了k 件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設計一個滿足要求的購物單.

輸入的第1 行，為兩個正整數，用一個空格隔開：

N 、m（其中N（<30000）表示總錢數，m(<25)為希望購買物品的個數。）

從第2 行到第m+1 行，第j 行給出了編號為j-1的物品的基本數據，每行有2 個非負整數v p（其中v 表示該物品的價格（v≤10000），p 表示該物品的重要度（1~5））

輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的

最大值（<100000000）

輸入數據： 1000 5

  800 2400 5300 5400 3200 2

輸出數據  3900

分析：01背包問題。對于每一個輸入都有買和不買兩種狀態。dp[i][j]表示對于前i件物品選擇部分購買限定總價不超過j元后，物品的價格與重要程度乘積的總和的最大值可得dp[m][n]即是所求的解。1.當前輸入的物品價格大于允許的最大總價j元，則不買，dp[i][j] = dp[i-1][j];2.當前輸入的物品價格小于等于允許的最大總價j元，考慮買或者不買兩種狀態，取物品的價格與重要程度乘積的總和最大的那個：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + t);

#include <iostream>