有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 c++ 背包入门题
C\u8bed\u8a00\uff0c\u7b97\u6cd5\u3001\u52a8\u6001\u89c4\u5212\uff1a\u6709\u4e00\u4e2a\u7bb1\u5b50\u7684\u5bb9\u91cf\u4e3av\uff08\u6b63\u6574\u6570\uff0c0<=v<=20000\uff09,\u540c\u65f6\u6709n\u4e2a\u7269\u54c1\uff080<n<=30\uff09\uff0c#include
#define N 30
int xiangzi(int n ,int V ,int a[]) //\u697c\u4e3b\u540e\u9762\u7684Vo\u6570\u7ec4\u5fc5\u987b\u653e\u8fdb\u9012\u5f52\u51fd\u6570\u91cc\u9762\u6216\u5b9a\u4e49\u6210\u5168\u5c40\u6570\u7ec4 \u53e6\u5916h[n]\u4ec0\u4e48\u60c5\u51b5\uff1f\uff1f
{
int minv,t,m=V;
if(n==0)
{
if(a[n]<=V) // V\u662f\u5269\u4f59\u7a7a\u95f4\u3002minv\u662f\u6240\u751f\u6700\u5c0f\u7a7a\u95f4\uff0c\u662f\u5f85\u6c42\u53d8\u91cf\uff0c\u800c\u4e0d\u662f\u5df2\u77e5\u7684 \uff0c\u4e0d\u80fdV<minv \u8fd9\u6837\u7528\u6765\u5224\u65ad\u3002
minv=V-a[n];
else
minv=V;
}
else
{
t=xiangzi(n-1,V,a);
if(a[n]<=V) //\u53ef\u80fda[n]\u6bd4V\u5927 \u5982\u679c\u6309\u697c\u4e3b\u7684\u7a0b\u5e8f\u6ca1\u5224\u65ad \u90a3\u4e48\u6b64\u65f6m\u5fc5\u5b9a\u5c0f\u4e8e0\uff0c\u6700\u540e\u7684minv\u80af\u5b9a\u662f\u4f1a\u5c0f\u96e80\u7684\u3002\u5e94\u8be5\u5148\u5224\u65ad \u6392\u9664\u8fd9\u79cd\u60c5\u77ff\u3002\u56e0\u6b64\u524d\u9762\u5b9a\u4e49m\u7684\u65f6\u5019\u53ef\u4ee5\u521d\u59cb\u5316m=V;
m=xiangzi(n-1,V-a[n],a); /*\u8003\u8651\u9009\u62e9\u8fd9\u4e2a\u7269\u4f53\u7684\u60c5\u51b5*/
if(t<m)
minv=t;
else
minv=m;
}
return minv;
}
void main()
{
int V;
int n,i,m,min;
int Vo[N];
printf("\u7bb1\u5b50\u7684\u5bb9\u91cfV\u4e3a\uff1a");
scanf("%d",&V);
printf("\u7269\u54c1\u7684\u79cd\u7c7b\u6570\u4e3a\uff1a");
scanf("%d",&n);
printf("\u7269\u54c1\u7684\u4f53\u79ef\u5206\u522b\u4e3a\uff1a\n");
for(i=0;i<n;i++)
scanf("%d",&Vo[i]); //"%d "\u6539\u6210\u201c%d\u201d d\u540e\u9762\u7684\u7a7a\u683c\u53bb\u6389\u3002\u4e0d\u597d\u610f\u601d \u6211\u5b66\u7684c++\uff0cc\u7684\u8bed\u6cd5\u4e0d\u600e\u4e48\u4e1c\uff0c \u53ea\u662f\u8c03\u8bd5\u51fa\u6765\u4e86\uff0c\u4e0d\u77e5\u9053\u539f\u56e0\uff0c\u53ef\u80fd\u8bed\u6cd5\u95ee\u9898\u5427\u3002
min=xiangzi(n-1,V,Vo);
printf("%d\n",min); //\u53e6\u5916\u522b\u5fd8\u4e86\u8f93\u51fa
system("pause");
}
\u5c31\u8fd9\u6837\u4e86\u3002\u3002\u3002
#include #include #include using namespace std;int dp[20001][30];int getdp(int restV, int index, int n, int volumn[]) {if (index == n) return 0;if (dp[restV][index] >= 0) {return dp[restV][index];}dp[restV][index] = getdp(restV, index + 1, n, volumn);if (restV >= volumn[index]) {dp[restV][index] = max(dp[restV][index], volumn[index] + getdp(restV - volumn[index], index + 1, n, volumn));}return dp[restV][index];}int main() {int V, n;int volumn[30];cin >> V >> n;for (int i = 0; i > volumn[i];}memset(dp, -1, sizeof(dp));cout << V - getdp(V, 0, n, volumn) << endl;}
题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是：
f[i][v] = Max
{
f[i 1][v]
f[i 1][v c[i]] + w[i]
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将
它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略
（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题
就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转
化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再
加上通过放入第i件物品获得的价值w[i]。
优化空间复杂度以上方法的时间和空间复杂度均为(V N)，其中时间复杂度应该已经不能
再优化了，但空间复杂度却可以优化到(N)1。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的
所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定
义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也
即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环
中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码
如下：
()
1 for i 1 to N
2 do for v V to 0
3 do f[v]=maxff[v],f[v-c[i]]+w[i]g;
其中的f[v] = maxff[v]; f[vc[i]]g一句恰就相当于我们的转移方程f[i][v] = maxff[i1][v]; f[i
1][v c[i]]g，因为现在的f[v-c[i]]就相当于原来的f[i 1][v c[i]]。如果将v的循环顺序从上面的逆
序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包
问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
1原文为O
1
斟酌题意“任取若干个，使余空最小”！再者没有限制性条件也无数据显示"若干个体积和＞V”！
故答案是：把30个物品全部装入。
注：题目是否有笔误？
绛旓細mark:array[1..maxn] of boolean;procedure dijkstra(v0:integer);beginfillchar(mark,sizeof(mark),false);for i:=1 to n do begind[i]:=a[v0,i];if d[i]<>0 then pre[i]:=v0 else pre[i]:=0;end;mark[v0]:=true;repeat {姣忓惊鐜竴娆″姞鍏ヤ竴涓1闆嗗悎鏈杩戠殑缁撶偣骞惰皟鏁村叾浠栫粨鐐圭殑鍙傛暟}m...
绛旓細鐢ㄥ瓙闂瀹氫箟鐘舵侊細鍗砯[i][v]琛ㄧず鍓峣浠剁墿鍝佹伆鏀惧叆涓涓閲忎负v鐨勮儗鍖呭彲浠ヨ幏寰楃殑鏈澶т环鍊笺傚垯鍏剁姸鎬佽浆绉绘柟绋嬩究鏄細f[i][v] = Max { f[i 1][v]f[i 1][v c[i]] + w[i]杩欎釜鏂圭▼闈炲父閲嶈锛屽熀鏈笂鎵鏈夎窡鑳屽寘鐩稿叧鐨勯棶棰樼殑鏂圭▼閮芥槸鐢卞畠琛嶇敓鍑烘潵鐨勩...
绛旓細闂鎻忚堪 鏈変竴涓瀛愬閲忎负V锛堟鏁存暟锛0锛滐紳V锛滐紳20000锛夛紝鍚屾椂鏈塶涓墿鍝侊紙0锛渘锛滐紳30锛夛紝姣忎釜鐗╁搧鏈変竴涓綋绉紙姝ｆ暣鏁帮級銆 瑕佹眰n涓墿鍝佷腑锛屼换鍙栬嫢骞蹭釜瑁呭叆绠卞唴锛屼娇绠卞瓙鐨勫墿浣欑┖闂翠负鏈灏忋 杈撳叆鏍煎紡 绗竴琛屼负涓涓暣鏁帮紝琛ㄧず绠卞瓙瀹归噺锛 绗簩琛屼负涓涓暣鏁帮紝琛ㄧず鏈塶涓墿鍝侊紱 ...
绛旓細1锛0-1鑳屽寘锛 姣忎釜鑳屽寘鍙兘浣跨敤涓娆℃垨鏈夐檺娆(鍙浆鍖栦负涓娆)锛欰.姹傛渶澶氬彲鏀惧叆鐨勯噸閲忋侼OIP2001 瑁呯闂 鏈変竴涓瀛愬閲忎负v(姝ｆ暣鏁帮紝o鈮鈮20000)锛屽悓鏃舵湁n涓墿鍝(o鈮鈮30)锛屾瘡涓墿鍝佹湁涓涓綋绉 (姝ｆ暣鏁)銆傝姹備粠 n 涓墿鍝佷腑锛屼换鍙栬嫢鍗冧釜瑁呭叆绠卞唴锛屼娇绠卞瓙鐨勫墿浣欑┖闂翠负鏈灏忋俵 鎼滅储鏂规硶 p...
绛旓細鏈変竴涓瀛愬閲忎负V锛堟鏁存暟锛0锛滐紳V锛滐紳20000锛夛紝鍚屾椂鏈塶涓墿鍝侊紙0锛渘锛滐紳30锛屾瘡涓墿鍝佹湁涓涓綋绉紙姝ｆ暣鏁帮級銆傝姹俷涓墿鍝佷腑锛屼换鍙栬嫢骞蹭釜瑁呭叆绠卞唴锛屼娇绠卞瓙鐨勫墿浣欑┖闂翠负鏈灏忋傛牱渚 杈撳叆锛24 涓涓暣鏁帮紝琛ㄧず绠卞瓙瀹归噺 6 涓涓暣鏁帮紝琛ㄧず鏈塶涓墿鍝 8 鎺ヤ笅鏉琛岋紝鍒嗗埆琛ㄧず杩檔 涓墿鍝...
绛旓細minv=m;} return minv;} void main(){ int V;int n,i,m,min;int Vo[N];printf("绠卞瓙鐨瀹归噺V涓锛");scanf("%d",&V);printf("鐗╁搧鐨勭绫绘暟涓猴細");scanf("%d",&n);printf("鐗╁搧鐨勪綋绉垎鍒负锛歕n");for(i=0;i<n;i++)scanf("%d",&Vo[i]); //"%d "鏀规垚鈥%d鈥 ...
绛旓細鏈変竴涓瀛愬閲忎负v锛堟鏁存暟锛0鈮鈮20000锛夛紝鍚屾椂鏈塶涓墿鍝侊紙0<n鈮30锛夛紝姣忎釜鐗╁搧鏈変竴涓綋绉紙姝ｆ暣鏁帮級銆傝姹備粠n涓墿鍝佷腑锛屼换鍙栬嫢骞蹭釜瑁呭叆绠卞唴锛屼娇绠卞瓙鐨勫墿浣欑┖闂翠负鏈灏忋傝緭鍏ワ細绠卞瓙鐨瀹归噺v 鐗╁搧鏁皀 鎺ヤ笅鏉琛岋紝鍒嗗埆琛ㄧず杩檔涓墿鍝佺殑浣撶Н 杈撳嚭锛氱瀛愬墿浣欑┖闂 杈撳叆杈撳嚭鏍蜂緥 杈撳叆锛24 6 8 3 12...
绛旓細j])a[j+x]=true;杩欏効鏈夌偣闂 閬囧埌j+x鐨勬椂鍊欏畠鏄痶rue,浣嗘槸瀹冨垰濂芥槸鏈塲閫氳繃X瑁呬笂鐨勩備竴涓鏄撴兂鍒扮殑瑙ｅ喅鍔炴硶鏄敤婊氬姩鏁扮粍锛屽彲鑳戒細瓒呮椂銆傚彟澶栦竴涓В鍐虫柟妗堟槸:鍔犲叆涓涓猺est鍙橀噺锛屾潵鐪嬩笂闈竴涓槸鍚︽槸鐢辫鍊间骇鐢熺殑銆傚叿浣撲唬鐮佸彲浠ユ煡鐪媠tones鐨勭浉鍏宠鏂囷紝鍐欏緱闈炲父鐨勬紓浜紝鎷垮埌杩欏効鏉ュ氨鏄ぇ璐㈡牎鐢ㄤ簡 ...
绛旓細鏈変竴涓瀛愬閲忎负V(姝ｆ暣鏁帮紝0鈮鈮20000锛夛紝鍚屾椂鏈塶涓墿鍝侊紙0鈮鈮30),姣忎釜鐗╁搧鏈変竴涓綋绉紙姝ｆ暣鏁帮級銆傝姹備粠n涓墿鍝佷腑锛屼换鍙栬嫢骞蹭釜瑁呭叆绠卞唴锛屼娇绠卞瓙鐨勫墿浣欑┖闂翠负鏈灏忋俒鏍蜂緥]杈撳叆锛 24 涓涓暣鏁帮紝琛ㄧず绠卞瓙瀹归噺 6 涓涓暣鏁帮紝琛ㄧず鏈塶涓墿鍝 8 鎺ヤ笅鏉琛岋紝鍒嗗埆琛ㄧず杩檔涓墿鍝佺殑鍚勮嚜...
绛旓細鑳屽寘闂 鏈変竴涓瀛愬閲忎负V锛鍚屾椂鏈塶涓墿鍝侊紝姣忎釜鐗╁搧鏈変竴涓綋绉锛堟鏁存暟锛夈傝璁′竴涓畻娉曞湪n涓墿鍝佷腑锛屼换鍙栬嫢骞蹭釜瑁呭叆绠卞唴锛屼娇绠卞瓙鐨勫墿浣欑┖闂翠负鏈灏忋傚姩鎬佽鍒 C#鐗堢畻娉 //浣撶Н琛細褰撲笉鍚岀殑鍙傜収鐗╂椂锛屽湪鍚勭浣撶Н绠卞瓙涓嬶紝鏈澶х殑鍗犵敤浣撶Н static int[,] vols = new int[100, 100];/// ...
