題目描述：
解題思路：
整體思路：
利用動態(tài)規(guī)劃，其目的就是將原問題分解成幾個子問題，通過求解簡單的子問題，把原問題給解決，就比如斐波那契數(shù)列方程：
f[i]=f[i-1]+f[i-2];
動態(tài)規(guī)劃的核心就是找到原問題與子問題的關系，并列出動態(tài)轉(zhuǎn)移方程。
實現(xiàn)方法：
這里我們可以定義一個二維數(shù)組，dp[i][j]表示對于背包容量為j的背包，前i個物品的最優(yōu)解，即最大價值。
對于一個物品，可以分兩種情況：
不選：對于dp[i][j]，不選第i個物品時，dp[i][j]的最優(yōu)解就是dp[i-1][j]的最優(yōu)解
選：如果選擇，我們就讓背包容量減去第i件的物品體積，讓dp加上物品價值，即dp[i][j]=dp[i-1][j-v[i]]+w[i];
這樣我們就得到了狀態(tài)轉(zhuǎn)移方程，如果要計算對于前N個物品背包容量為V的背包的最優(yōu)解，只需要一層一層往前推，通過前面的子問題，求得最終答案。
狀態(tài)轉(zhuǎn)移方程:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);文章來源：http://www.zghlxwxcb.cn/news/detail-512656.html
代碼和注釋：
#include <iostream>
using namespace std;
int dp[1010][1010];
int v[1010],w[1010];//體積和價值
int main(){
int N,V;
int i,j;
//輸入數(shù)據(jù)
cin>>N>>V;//商品個數(shù)和背包容量
for(i=1;i<=N;i++)
{
cin>>v[i]>>w[i];//體積和價值
}
for(i=1;i<=N;i++)//依次遍歷從第1個物品到第N個物品
{
for(j=1;j<=V;j++)//依次遍歷從0~背包容量V
{
if(j<v[i])//如果背包容量小于物品體積
{
dp[i][j]=dp[i-1][j];//最優(yōu)解就是上一個物品時的最優(yōu)解
}
else//否則就是背包容量大于等于物品體積
{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);//拿或者不拿，選最優(yōu)
}
}
}
cout<<dp[N][V]<<endl;//輸出前N個商品,背包容量為V的最優(yōu)解
return 0;
}
參考自：https://blog.csdn.net/q1411687596/article/details/104827473文章來源地址http://www.zghlxwxcb.cn/news/detail-512656.html
完結(jié)，撒花撒花…
到了這里，關于動態(tài)規(guī)劃——01背包問題（C++實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
