N件物品驮吱，沒見有重量Wi茧妒，價(jià)值Vi；選其中幾件放入容量為M的背包中左冬，求價(jià)值的最值≈叫停——經(jīng)典背包問題
背包問題分三類：
1.01背包：每件物品僅一件拇砰，可以不將背包裝滿（要么取0件要么1件）
2.完全背包：每件物品無限件，可以不將背包裝滿狰腌。
3.多重背包：每件物品可一定數(shù)量件除破，可不將背包裝滿。
此片詳解01背包琼腔。
建一個(gè)N*（M+1）的數(shù)組dp[N][M]瑰枫，物品從第一個(gè)開始遍歷依次裝入背包。
行下標(biāo)從0到N - 1丹莲，表示從第一種物品裝到底N - 1中物品光坝，列從0到M，表示包中物品重量從0到M甥材。
關(guān)鍵公式：dp [ i ] [ j ] = max / min ( dp [ i - 1 ] [ j ] , dp[ i - 1 ] [ j - W[ i ] ] + V [ i ] ) ;
這個(gè)公式什么意思呢盯另？max/min是根據(jù)題目不同選擇采取最大或最小值。主要是看()中的部分洲赵。dp[i - 1][ j ]指包內(nèi)重量為j鸳惯，但是包中不包含第i種物品。dp[i - 1][j - w[ i ]] + v[ i ]指的是包內(nèi)裝有第i種物品叠萍，那么這種情況下芝发，包內(nèi)總重量為j的情況下前i - 1中物品的重量就應(yīng)該是j減去當(dāng)前物品的重量，物品價(jià)值就應(yīng)該是前i - 1種物品的總價(jià)值加上當(dāng)前物品的價(jià)值苛谷，那么最大或最小價(jià)值就是包內(nèi)裝當(dāng)前物品和不裝當(dāng)前物品兩種情況中的最值辅鲸。
典例：http://acm.hdu.edu.cn/showproblem.php?pid=2602
題意：可理解為背包問題，一共n樣物品各有其重量w[ i ]和價(jià)值v[ i ]抄腔，給出背包容量m求出背包所容最大的價(jià)值瓢湃。
分析：每件物品放入或不放入背包理张，若不放入背包，則dp[ i ] [ j ]的值即為dp[ i - 1 ] [ j ]绵患。若是放入背包雾叭，則需要在當(dāng)重量為 j - w[ i ] 的基礎(chǔ)上加入物品 i，價(jià)值也應(yīng)是在dp[ i ] [ j - w [ i ] ] 的值上再加上物品 i 的價(jià)值v [ i ] 落蝙，其價(jià)值即為dp[ i - 1 ] [ j - w[ i ] ]+ v[ i ] 织狐。再取兩個(gè)之中的較大者即得到最優(yōu)解。
代碼實(shí)現(xiàn)：
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int w[1005],v[1005],dp[1005][1005];
int main()
{
int T,n,m;
cin>>T;
while(T--)
{
cin>>n>>m;
//注意先輸入價(jià)值筏勒！因?yàn)檫@個(gè)WA好幾次
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
cin>>w[i];
memset(dp,0,sizeof(dp));//dp數(shù)組初始化
for(int i=1;i<=n;i++) //物品從第一個(gè)開始遍歷
{
for(int j=0;j<=m;j++)//質(zhì)量從0開始移迫，數(shù)據(jù)有重量為0，價(jià)值不為零的情況
{
//能裝下w[i]時(shí)管行，比較dp[i-1][j]和dp[i-1][j-w[i]]+v[i]
if(w[i]<=j) {dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}
//裝不下則dp[i][j]=dp[i-1][j]
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}
